Avner Magen (University of Toronto ):
Sublinear Geometric Algorithms
With the current information explosion, massive data sets are now pervasive
and they pose new challenges in algorithm design. For example, a linear
time algorithm, which was considered as the ultimate efficiency goal for many
years, could easily be unacceptably slow for massive data sets. It is
thus necessary to develop algorithms that use sublinear
amount of time or space resources. Recently, great progress has been made
in this research direction,and the study of sublinear algorithms has emerged
as a field unto itself. In computational geometry, such sublinear efficiency
is traditionally achieved by performing a one-time preprocessing
of the data. This is often a satisfactory solution, but is
of little use when datasets are so massive that examining the
whole input -- let alone preprocessing it -- is out of the question.
We initiate an investigation of sublinear algorithms in the domain
of geometry and show that, for many classical geometric problems,
the standard representation of the input or the standard data-structures supporting it, allow for sublinear algorithms. These algorithms randomly sample a
small fraction of the input and do not require any preprocessing.
We present randomized algorithms for the following problems:
detecting the intersection of convex 3D polyhedra; ray- shooting
and nearest-neighbor with respect to polyhedra; point location in
two-dimensional planar subdivision. All presented
algorithms run in expected time O(sqrt n), where n is the
size of the input. We also provide approximation algorithms with similar
running times for finding the volume of a polytope
and for finding the shortest path between two points on the
boundary a polytope. In a different setting, we look at the well known
problem of computing the weight of the minimal spanning tree in
Euclidean space. We show how to approximate this
weight in O(sqrt n) time. Prior to these results, the problems described above
had only linear or superlinear algorithms. The talk contains results
achieved together with B. Chazelle, D. Liu, A. Czumaj, F. Ergun,
L. Fortnow, I. Newman, R. Rubinfeld and C. Sohler.