Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

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

Action:

login to update

Options:




Library Locked Library locked




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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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)
[Library]
Created
01/05/2010 10:46:55 AM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section