MPI-INF D1 Publications: Proceedings Article: Exact Geometric-Topological Analysis of Algebraic Surfaces

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

Options:

Goto entry point

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
Attachment(s):	bks_egtaoas.pdf (313.57 KB)
Booktitle*:	Proceedings of the 24th ACM Symposium on Computational Geometry

Event, URLs

URL of the conference:	http://www.umiacs.umd.edu/conferences/socg2008/index.shtml
URL for downloading the paper:
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

Edit History (please click the blue arrow to see the details)

	Editor(s) Eric Berberich	Created 06/24/2008 06:32:10 PM
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

Attachment Section

Attachment Section

View attachments here:

bks_egtaoas.pdf

bks_egtaoas.pdf