MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Geismann, Nicola
Hemmer, Michael
Schömer, Elmar
dblp
dblp
dblp
Editor(s):
BibTeX cite key*:
ghs-qsi-01
Title, Booktitle
Title*:
Computing a 3-dimensional Cell in an Arrangement of Quadrics: Exactly and Actually!
Booktitle*:
Proceedings of the 17th Annual Symposium on Computational Geometry (SCG-01)
Event, URLs
Conference URL::
http://www.cs.tufts.edu/EECS/scg01
Downloading URL:
Event Address*:
Boston, Massachusetts
Language:
English
Event Date*
(no longer used):
June, 3-5
Organization:
ACM SIGACT and SIGGRAPH
Event Start Date:
21 January 2022
Event End Date:
21 January 2022
Publisher
Name*:
ACM
URL:
Address*:
New York
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
264-273
Year*:
2001
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We present two approaches to the problem of calculating a cell in a
3-dimensional arrangement of quadrics. The first approach solves the
problem using rational arithmetic. It works with reductions to
planar arrangements of algebraic curves. Degenerate
situations such as tangential intersections and self-intersections of
curves are intrinsic to the planar arrangements we obtain.
The coordinates of the intersection points are given by
the roots of univariate polynomials.
We succeed in locating all intersection points either by extended
local box hit counting arguments or by globally characterizing
them with simple square root expressions.
The latter is realized by a clever factorization of the univariate
polynomials. Only the combination of these two results
facilitates a practical and implementable algorithm.

The second approach operates directly in 3-space by applying
classical solid modeling techniques. Whereas the first
approach guarantees a correct solution in every case the second one
may fail in some degenerate situations. But with the
help of verified floating point arithmetic it can detect these
critical cases and is faster if the quadrics are in general
position.
Download
Access Level:

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{ghs-qsi-01,
AUTHOR = {Geismann, Nicola and Hemmer, Michael and Sch{\"o}mer, Elmar},
TITLE = {Computing a 3-dimensional Cell in an Arrangement of Quadrics: Exactly and Actually!},
BOOKTITLE = {Proceedings of the 17th Annual Symposium on Computational Geometry (SCG-01)},
PUBLISHER = {ACM},
YEAR = {2001},
ORGANIZATION = {ACM SIGACT and SIGGRAPH},
PAGES = {264--273},
ADDRESS = {Boston, Massachusetts},
}


Entry last modified by Uwe Brahm, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Elmar Schoemer
Created
03/13/2002 02:36:40 PM
Revisions
3.
2.
1.
0.
Editor(s)
Uwe Brahm
Elmar Schoemer
Elmar Schoemer
Elmar Schoemer
Edit Dates
04/29/2002 02:49:59 PM
13/03/2002 15:02:30
13/03/2002 14:43:08
13/03/2002 14:36:41