# 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

**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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 188 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: **http://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},`

`}`