MPI-I-2007-1-001
Linear-time reordering in a sweep-line algorithm for algebraic curves intersecting in a common point
Berberich, Eric and Kettner, Lutz
July 2007, 20 pages.
.
Status: available - back from printing
The Bentley Ottmann sweep line algorithm is a standard tool to compute
the arrangement of algebraic curves in the plane. If degenerate
positions are not excluded from the input, variants of this algorithm
must, among other things, handle $k \geq 2$ curves intersecting
simultaneously in a single intersection point. In that situation, the
algorithm knows the order of the curves immediately left of the
intersection point and needs to compute the order immediately right of
the intersection point.
Segments and lines can be reordered efficiently in linear time by
simply reversing their order, except for overlapping segments.
Algebraic curves can be sorted with $O(k \log k)$ geometric
comparisons in their order immediately right of the intersection
point. A previous result shows that algebraic curves
whose degree is at most $d$ can be reordered in $O(d^2 k)$ time, which
is for constant $d$ better than sorting.
In this paper, we improve the complexity of the reordering of
algebraic curves to $O(k)$ time, i.e., independent of the degree of
the algebraic curves. The maybe surprising implication is that
algebraic curves, even of unbounded algebraic degree, cannot realize
all possible permutations of their vertical order while passing
through a common intersection from left to right. We give a short
example for an infeasible permutation.
Both linear time algorithms require the knowledge of the intersection
multiplicities of curves that are neighbors immediately left of the
intersection point, i.e., $k-1$ intersection multiplicities.
-
- Attachement: 16012496.pdf (188 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2007-1-001
BibTeX
@TECHREPORT{BerberichKettner2007,
AUTHOR = {Berberich, Eric and Kettner, Lutz},
TITLE = {Linear-time reordering in a sweep-line algorithm for algebraic curves intersecting in a common point},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-2007-1-001},
MONTH = {July},
YEAR = {2007},
ISSN = {0946-011X},
}