Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Linear-time reordering in a sweep-line algorithm for algebraic curves intersecting in a common point

Berberich, Eric and Kettner, Lutz

MPI-I-2007-1-001. July 2007, 20 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.

References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-2007-1-001.pdf188 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  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},