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:








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



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
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)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
bks_egtaoas.pdf