Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update 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 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

 (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},
}