de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Exact, Efficient and Complete Arrangement Computation for Cubic Curves

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44369

Eigenwillig,  Arno
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44766

Kettner,  Lutz
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45414

Schömer,  Elmar
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45758

Wolpert,  Nicola
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Eigenwillig, A., Kettner, L., Schömer, E., & Wolpert, N. (2006). Exact, Efficient and Complete Arrangement Computation for Cubic Curves. Computational Geometry, 35, 36-73.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-22C2-8
Abstract
The Bentley-Ottmann sweep-line method can compute the arrangement of planar curves, provided a number of geometric primitives operating on the curves are available. We discuss the reduction of the primitives to the analysis of curves and curve pairs, and describe efficient realizations of these analyses for planar algebraic curves of degree three or less. We obtain a \emph{complete}, \emph{exact}, and \emph{efficient\/} algorithm for computing arrangements of cubic curves. Special cases of cubic curves are conics as well as implicitized cubic splines and B\'ezier curves. The algorithm is \emph{complete\/} in that it handles all possible degeneracies such as tangential intersections and singularities. It is \emph{exact\/} in that it provides the mathematically correct result. It is \emph{efficient\/} in that it can handle hundreds of curves with a quarter million of segments in the final arrangement. The algorithm has been implemented in C\texttt{++} as an \textsc{Exacus} library called \textsc{CubiX}.