94-11 A Pseudo-algorithmic Separation of Lines from Pseudo-lines

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