Robust interval algorithm for curve intersections

Chun Yi Hu*, Takashi Maekawa, Evan C. Sherbrooke, Nicholas M. Patrikalakis

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

58 Citations (Scopus)


In this paper, we develop and study a robust algorithm for computing intersections of two planar interval polynomial curves. The intersection problems include well-conditioned transveral intersections as well as ill-conditioned cases such as tangential and overlapping intersections. Key components of our methods are the reduction of the intersection problems into solving systems of nonlinear interval polynomial equations which consist of m equations with n unknowns. An earlier interval nonlinear polynomial solver for balanced system based on Bernstein subdivision method coupled with rounded interval arithmetic is extended to solve unbalanced systems. The solver provides results with numerical certainty and verifiability. Examples illustrate our techniques.

Original languageEnglish
Pages (from-to)495-506
Number of pages12
JournalCAD Computer Aided Design
Issue number6-7
Publication statusPublished - 1996
Externally publishedYes


  • CAD
  • CAGD
  • CAM
  • Curve intersection
  • Interval polynomial solver
  • Overlapping
  • Robustness
  • Rounded interval arithmetic
  • Tangency

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Robust interval algorithm for curve intersections'. Together they form a unique fingerprint.

Cite this