## DIMACS TR: 94-11

## A Pseudo-algorithmic Separation of Lines from Pseudo-lines

### Authors: William Steiger, Ileana Streinu

**
ABSTRACT
**

The x-sorting problem for lines is: sort the
x-coordinates of the intersection points of n planar lines. A
similar problem can be defined for pseudo-lines. We show a lower
bound of \Omega(n^2 \log n) for x-sorting pseudo-lines and the
existence of a quadratic decision tree of depth O(n^2) for
x-sorting lines. Let X and Y be two n element sets and let
X+Y = { x+y | x \in X, y \in Y }.
Sorting X+Y is a particular case of x-sorting lines.
Fredman has shown the existence of an O(n^2)-depth
decision tree for this case and Lambert has given a method
to actually find the O(n^2) comparisons. Here we give another very
simple divide and conquer algorithm for sorting X+Y with O(n^2)
comparisons which only needs O(n^2 log n) time.

Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-11.ps

DIMACS Home Page