Please note that eDoc will be permanently shut down in the first quarter of 2021!      Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents



ID: 314461.0, MPI für Informatik / Algorithms and Complexity Group
Exact, Efficient and Complete Arrangement Computation for Cubic Curves
Authors:Eigenwillig, Arno; Kettner, Lutz; Schömer, Elmar; Wolpert, Nicola
Language:English
Date of Publication (YYYY-MM-DD):2006
Title of Journal:Computational Geometry
Volume:35
Start Page:36
End Page:73
Copyright:Copyright © 2005 Elsevier B.V. All rights reserved.
This article has been published in Computational Geometry 35(1-2), August 2006,
Pages 36-73.
Review Status:Peer-review
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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}.
Last Change of the Resource (YYYY-MM-DD):2007-02-10
External Publication Status:published
Document Type:Article
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C1256428004B93B8-9FBA65AC1148D2AEC1257176004AA8EE-...
ISSN:0925-7721
Full Text:
You have privileges to view the following file(s):
EKSW-Cubics-CGTA-authprep.pdf  [493,00 Kb] [Comment:file from upload service]  
 
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.