94-22 Randomizing Optimal Geometric Algorithms (Extended Abstract)

DIMACS TR: 94-22

Randomizing Optimal Geometric Algorithms (Extended Abstract)

Authors: Larry Shafer and William Steiger

ABSTRACT
The parametric search technique of Megiddo has been used to produce optimal deterministic algorithms for a number of geometric problems, e.g., planar ham-sandwich cuts and slope selection. Unfortunately these algorithms inherit huge constants from the parallel algorithms used by the technique. Here we give very simple randomized versions and show (experimentally and analytically) that the constants in the asymptotically optimal running times are small. These randomized versions could therefore be argued to be the methods of choice for their respective tasks. We also give a simple, new, randomized planar convex hull algorithm whose expected running time matches the average-case complexity of good deterministic algorithms, and with good protection (probability --> 0 quickly) against worst-case behaviour.

Also available as LCSR-TR-212.

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

DIMACS Home Page