MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Berberich, Eric
Kerber, Michael
Sagraloff, Michael		dblp
dblp
dblp
Editor(s):
Teillaud, Monique
Welzl, Emo		dblp
dblp
Not MPII Editor(s):
Teillaud, Monique
Welzl, Emo
BibTeX cite key*:
bks-egtaas-08
Title, Booktitle
Title*:
Exact Geometric-Topological Analysis of Algebraic Surfaces
bks_egtaoas.pdf (313.57 KB)
Booktitle*:
Proceedings of the 24th ACM Symposium on Computational Geometry
Event, URLs
Conference URL::
http://www.umiacs.umd.edu/conferences/socg2008/index.shtml
Downloading URL:
Event Address*:
College Park Maryland, USA
Language:
English
Event Date*
(no longer used):
Organization:
Association for Computing Machinery (ACM)
Event Start Date:
9 June 2008
Event End Date:
11 June 2008
Publisher
Name*:
ACM
URL:
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
June
Pages:
164-173
Year*:
2008
VG Wort Pages:
10
ISBN/ISSN:
978-1-60558-071-5
Sequence Number:
DOI:
10.1145/1377676.1377703
Note, Abstract, ©
(LaTeX) Abstract:
We present a method to compute the exact topology of a real algebraic surface
$S$, implicitly given by a polynomial $f \in \mathbb{Q}[x,y,z]$ of arbitrary
degree $N$.
Additionally, our analysis provides geometric information as it
supports the computation of arbitrary precise samples of $S$
including critical points.
We use a projection approach,
similar to Collins' cylindrical algebraic decomposition (cad).
In comparison we reduce the number of output cells to $O(N^5)$ by constructing
a special planar arrangement instead of a full cad in the projection plane.
Furthermore, our approach applies numerical and combinatorial methods to
minimize costly symbolic computations. The algorithm handles all sorts of
degeneracies without transforming the surface into a generic position.
We provide a complete implementation of the algorithm, written in C++. It shows
good performance for many well known examples from algebraic geometry.
Keywords:
Algebraic surfaces, exact geometric computation, topology computation, cylindrical algebraic decomposition
Copyright Message:
Copyright ACM, 2008.
This is the authors' version of the work.
It is posted here by permission of ACM for your personal use.
Not for redistribution. The definitive version was published in the
Proceedings of the twenty-fourth annual symposium on Computational geometry
(SoCG 2008),
http://doi.acm.org/10.1145/1377676.1377703
Download
Access Level:
Public

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{bks-egtaas-08,
AUTHOR = {Berberich, Eric and Kerber, Michael and Sagraloff, Michael},
 EDITOR = {Teillaud, Monique and Welzl, Emo},
 TITLE = {Exact Geometric-Topological Analysis of Algebraic Surfaces},
 BOOKTITLE = {Proceedings of the 24th ACM Symposium on Computational Geometry},
 PUBLISHER = {ACM},
 YEAR = {2008},
 ORGANIZATION = {Association for Computing Machinery (ACM)},
 PAGES = {164--173},
 ADDRESS = {College Park Maryland, USA},
 MONTH = {June},
 ISBN = {978-1-60558-071-5},
 DOI = {10.1145/1377676.1377703},
}

Entry last modified by Michael Kerber, 03/03/2009
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)
Eric Berberich		Created
06/24/2008 18:32:10
Revisions
3.
2.
1.
0.
Editor(s)
Michael Kerber
Michael Kerber
Eric Berberich
Eric Berberich
Edit Dates
06/26/2008 03:14:46 PM
06/24/2008 10:02:14 PM
06/24/2008 06:35:45 PM
06/24/2008 06:32:10 PM

File Attachment Icon
bks_egtaoas.pdf