MPI-INF D1 Publications: Journal Article: An efficient algorithm for the stratification and triangulation of an algebraic surface

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

Options:

Library locked

Goto entry point

Author, Editor(s)

Author(s):

Berberich, Eric
Kerber, Michael
Sagraloff, Michael

dblp
dblp
dblp

BibTeX cite key*:

bks-cgta-2009

Title

Title*:

An efficient algorithm for the stratification and triangulation of an algebraic surface

Journal

Journal Title*:	Computational Geometry: Theory and Applications (CGTA)	Journal's URL:	www.elsevier.com/locate/comgeo
Download URL for the article:	http://dx.doi.org/	Language:	English

Publisher

Publisher's Name:	Elsevier	Publisher's URL:	http://www.elsevier.com
Publisher's Address:	Amsterdam, Netherlands	ISSN:	0925-7721

Vol, No, pp, Date

Volume*:	43	Number:	3
Publishing Date:	April 2010
Pages*:	257-278	Number of VG Pages:	20
Page Start:	257	Page End:	278
Sequence Number:		DOI:	10.1016/j.comgeo.2009.01.009

Note, Abstract, ©

Note:
(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 total degree~$N$. Additionally, our analysis provides geometric information as it supports the computation of arbitrary precise samples of $S$ including critical points. We compute a stratification $\Omega_S$ of $S$ into $O(N^5)$ nonsingular cells, including the complete adjacency information between these cells. This is done by a projection approach. We construct a special planar arrangement $\mathcal{A}_S$ with fewer cells than a 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. Based on $\Omega_S$ we also compute a simplicial complex which is isotopic to~$S$. A complete C++-implementation of the stratification algorithm is presented. It shows good performance for many well-known examples from algebraic geometry.
URL for the Abstract:
Categories, Keywords:	Algebraic surfaces, exact geometric computation, topology computation, cylindrical algebraic decomposition
HyperLinks / References / URLs:
Copyright Message:
Personal Comments:
Download Access Level:	Public

Correlation

MPG Unit:	Max-Planck-Institut für Informatik

MPG Subunit:	Algorithms and Complexity Group
Audience:	popular
Appearance:	MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{bks-cgta-2009,
AUTHOR = {Berberich, Eric and Kerber, Michael and Sagraloff, Michael},
TITLE = {An efficient algorithm for the stratification and triangulation of an algebraic surface},
JOURNAL = {Computational Geometry: Theory and Applications (CGTA)},
PUBLISHER = {Elsevier},
YEAR = {2010},
NUMBER = {3},
VOLUME = {43},
PAGES = {257--278},
ADDRESS = {Amsterdam, Netherlands},
MONTH = {April},
ISBN = {0925-7721},
DOI = {10.1016/j.comgeo.2009.01.009},
}

Entry last modified by Michael Sagraloff, 03/22/2011

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

	Editor(s) [Library]	Created 01/05/2010 10:46:55
Revisions 4. 3. 2. 1. 0.	Editor(s) Michael Sagraloff Michael Sagraloff Anja Becker Eric Berberich Eric Berberich	Edit Dates 03/22/2011 05:58:02 PM 20.01.2011 10:02:54 01.03.2010 13:39:03 01/20/2010 12:12:01 PM 01/05/2010 10:46:55 AM

Attachment Section