pollack@GEOMETRY.CIMS.NYU.EDU (Ricky Pollack) (01/08/91)
SIXTEENTH COMPUTATIONAL GEOMETRY DAY
Friday, February 8, 1991
New York University
Courant Institute of Mathematical Sciences
Room 109, Warren Weaver Hall
251 Mercer St., New York, NY 10012
10:00-10:30 - Coffee (13th floor lounge)
10:30-11:15 Jiri Matousek, Charles University and Georgia Tech
Efficient Partition Trees
11:30-12:15 Joseph O'Rourke
The Star Unfolding of a Polytope
12:30-2:00 - Lunch
2:00-3:00 Open Problem Session
3:00-3:45 Laszlo Lovasz, Eotvos University and Princeton University
Random Walks in Convex Bodies
4:00-5:00 - Wine and Cheese Reception in the 13th floor lounge
For more information contact: Richard Pollack (212) 998-3167
pollack@geometry.nyu.edu
****************************************************************************
Jiri Matousek, Charles University and Georgia Tech
Efficient Partition Trees
We prove a theorem on partitioning point sets in E^d (d fixed) and give
an efficient construction of partition trees based on it. Such a partition
tree for n points uses O(n) space, can be constructed in O(nlog n)
time (both by a randomized and a deterministic algorithm, the randomized
construction being reasonably simple), and it can be used to answer simplex
range queries (counting or general semigroup ones) in time
O(n^{1-1/d}(log n)^{O(1)}). If we allow O(n^{1+delta}) preprocessing
time, where delta is some positive constant, a more complicated data
structure yields query time O(n^{1-1/d}(loglog n)^{O(1)}). For dimensions
d=2,3 and if the weights of the points lie in a group, we get query time
O(n^{1-1/d}2^{O(log^*n)}). This attains the lower bounds due to Chazelle
up to polylogarithmic factors, improving the recent results of Chazelle,
Sharir and Welzl, making the preprocessing deterministic without loss of
efficiency and simplifying the query answering algorithm. Tradeoff between
preprocessing (and storage) and query time is also possible. The partition
result is also applied for a deterministic computation of epsilon-cuttings.
E.g., given a collection of n lines in the plane and a parameter r, the
plane can be subdivided into O(r^2) triangles, each intersected by at most
n/r of the given lines, in time O(n^{1/2}r^{3/2}(log n)^{O(1)}+nlog r),
thus in almost linear time for r<n^{1/3}.
******************************************************************************
k Joseph O'Rourke, Smith College
The Star unfolding of a Simple Polytope
The star unfolding of a polytope with respect to a point x is obtained
by cutting the surface along the shortest paths from x to every vertex,
and flattening the surface on the plane. We establish two main properties
of the star unfolding:
* It does not self-overlap: its boundary is a simple polygon.
* The ridge tree in the unfolding, which is the locus of
points with more than one shortest path from x, is precisely the
Voronoi diagram of the images of x, restricted to the unfolding.
These two properties permit the conceptual simplification of algorithms
concerned with shortest paths on polytopes, and often a worst-case complexity
improvement as well:
* The construction of the ridge tree (in preparation for
shortest path queries, for instance) can be achieved by an especially
simple O(n^2) algorithm. This is no worstcase improvement, but a
considerable simplification nonetheless.
* The exact set of all shortest path ``edge sequences'' on a polytope
can be found in O(n^6 log n) time, an improvement of O(n) over the
previous best algorithm.
* The diameter of a polygon can be found in O(n^9 log n)
time, again an improvement of about O(n).
Our results suggest conjectures on unfoldings of smooth convex surfaces.
This is joint work with Boris Aronov.
*****************************************************************************
Laszlo Lovasz, Eotvos University and Princeton Universlty
Random Walks in Convex Bodies
Dyer, Frieze and Kannan designed a polynomial time randomized algorithm
to approximate the volume of a convex body K in R^n. A crucial step
of the algorithm is to generate a random point in a convex body. This is
achieved by making a random walk on the lattice points inside the body.
The analysis of the algorithm depends on two factors: a theorem of Sinclair
and Jerrum on the mixing rate of time-reversible Markov chains and on an
isoperimetric inequality for subsets of a convex body. Several improvements
of the original algorithm were given by Lovasz and Simonovits, Khachiyan
and Karzanov, and then again by Dyer, Frieze and Kannan.
We describe related but more efficient algorithms to generate a random point
in a convex body. The analysis depends on certain extensions of the Jerrum--
Sinclair theorem and on various isoperimetric inequalities.