de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

#### An Exact, Complete and Efficient Implementation for Computing Planar Maps of Quadric Intersection Curves

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44118

Berberich,  Eric
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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

Hemmer,  Michael
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;

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

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

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Berberich, E., Hemmer, M., Kettner, L., Schömer, E., & Wolpert, N. (2005). An Exact, Complete and Efficient Implementation for Computing Planar Maps of Quadric Intersection Curves. In 21st Annual Symposium on Computational Geometry (SCG'05) (pp. 99-106). New York, USA: ACM.

We present the first exact, complete and efficient implementation that computes for a given set $P=\{p_1,\dots,p_n\}$ of quadric surfaces the planar map induced by all intersection curves $p_1\cap p_i$, $2\leq i\leq n$, running on the surface of $p_1$. The vertices in this graph are the singular and $x$-extreme points of the curves as well as all intersection points of pairs of curves. Two vertices are connected by an edge if the underlying points are connected by a branch of one of the curves. Our work is based on and extends ideas developed in~[20] and~[9]. Our implementation is {\em complete} in the sense that it can handle all kind of inputs including all degenerate ones where intersection curves have singularities or pairs of curves intersect with high multiplicity. It is {\em exact} in that it always computes the mathematical correct result. It is {\em efficient} measured in running times.