Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

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

Action:

login to update
Options:








Author, Editor(s)
Author(s):
Eigenwillig, Arno
Kettner, Lutz
Schömer, Elmar
Wolpert, Nicola		dblp
dblp
dblp
dblp
Not MPG Author(s):
Schömer, Elmar

BibTeX cite key*:

eksw-eecaccc-06

Title

Title*:

Exact, Efficient and Complete Arrangement Computation for Cubic Curves


EKSW-Cubics-CGTA-authprep.pdf (493.4 KB)

Journal

Journal Title*:

Computational Geometry
Journal's URL:

http://www.elsevier.com/locate/comgeo

Download URL
for the article:

http://dx.doi.org/10.1016/j.comgeo.2005.10.003
Language:

English

Publisher

Publisher's
Name:

Elsevier
Publisher's URL:

http://www.elsevier.com/

Publisher's
Address:

Amsterdam, The Netherlands
ISSN:

0925-7721

Vol, No, pp, Date

Volume*:

35
Number:

1-2

Publishing Date:

August 2006

Pages*:

36-73
Number of
VG Pages:

126

Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

The Bentley-Ottmann sweep-line method can compute the
arrangement of planar curves, provided a number of geometric
primitives operating on the curves are available. We discuss the
reduction of the primitives to the analysis of curves and curve pairs,
and describe efficient realizations of these analyses
for planar algebraic curves of degree three or less. We
obtain a \emph{complete}, \emph{exact}, and \emph{efficient\/}
algorithm for computing arrangements of cubic curves.
Special cases of cubic curves are
conics as well as implicitized cubic splines and B\'ezier curves.

The algorithm is \emph{complete\/} in that it handles all possible
degeneracies such as tangential intersections and singularities.
It is \emph{exact\/} in that it provides the mathematically correct
result. It is \emph{efficient\/} in that it can handle hundreds of
curves with a quarter million of segments in the final arrangement.
The algorithm has been implemented in C\texttt{++} as an \textsc{Exacus}
library called \textsc{CubiX}.

URL for the Abstract:

http://dx.doi.org/10.1016/j.comgeo.2005.10.003

Categories,
Keywords:

Arrangements, Agebraic curves, Sweep-line algorithm, Robustness, Exact geometric computation

HyperLinks / References / URLs:

http://dx.doi.org/10.1016/j.comgeo.2005.10.003

Copyright Message:

Copyright © 2005 Elsevier B.V. All rights reserved.
This article has been published in Computational Geometry 35(1-2), August 2006, Pages 36-73.

Personal Comments:


Download
Access Level:

Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{eksw-eecaccc-06,
AUTHOR = {Eigenwillig, Arno and Kettner, Lutz and Sch{\"o}mer, Elmar and Wolpert, Nicola},
 TITLE = {Exact, Efficient and Complete Arrangement Computation for Cubic Curves},
 JOURNAL = {Computational Geometry},
 PUBLISHER = {Elsevier},
 YEAR = {2006},
 NUMBER = {1-2},
 VOLUME = {35},
 PAGES = {36--73},
 ADDRESS = {Amsterdam, The Netherlands},
 MONTH = {August},
 ISBN = {0925-7721},
}

Entry last modified by Christine Kiesel, 02/07/2007
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)
Arno Eigenwillig		Created
05/22/2006 15:35:29
Revisions
2.
1.
0.

Editor(s)
Christine Kiesel
Arno Eigenwillig
Arno Eigenwillig

Edit Dates
07.02.2007 10:19:12
06/07/2006 05:45:00 PM
05/22/2006 03:35:29 PM

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

File Attachment Icon
EKSW-Cubics-CGTA-authprep.pdf