pollack@GEOMETRY.CIMS.NYU.EDU (Ricky Pollack) (10/26/90)
FIFTEENTH COMPUTATIONAL GEOMETRY DAY
Friday, November 9, 1990
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 Pankaj K. Agarwal, Duke University
Applications of a new Space Partitioning Technique
11:30-12:15 Godfried Toussaint, McGill University
Computing Extremal Transversals of Sets
12:30-2:00 - Lunch
2:00-3:00 Open Problem Session
3:00-3:45 Ketan Mulmuley, University of Chicago
Dynamic Problems in Randomized Coimputational Geometry
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
****************************************************************************
Pankaj K. Agarwal, Duke University
Applications of a New Partitioning Technique
Recently Chazelle, Sharir and Welzl proposed a new algorithm for simplex
range searching based on a clever partitioning scheme. In this talk we
show that their partitioning scheme cane be applied to a variety of
problems including ray shooting in 2D and 3D, hidden surface removal, and
computing spanning trees of low stabbing number.
* This is a joint work with Micha Sharir
*****************************************************************************
Godfried Toussaint, McGill University
Computing Extremal Transversals of Sets
Recent results on computing extremal transversals of sets will be presented.
We show how the shortest line segment that intersects a set of n given
line segments can be computed in O(n (log n)**2) time. If the line
segments do not intersect this algorithm may be trimmed to run in O(n log n)
time. We also show that given n lines the shortest transversal can be computed
in O(n log n) time. Finally we will mention some results on computing the
convex hull of a set of lines, i.e., the smallest convex polygon intersecting
the O(n**2) intersection points I of the line arrangement. Atallah as well as
Lee & Lin showed independently that the convex hull of I contains O(n) vertices
and can be computed in O(n log n) time. It turns out that for a random
arrangement of lines the expected number of convex hull vertices is O(1) and
this fact can be used to obtain an algorithm for computing the convex hull of
I in linear expected time.
*****************************************************************************
Ketan Mulmuley, University of Chicago
Dynamic Problems in Randomized Computational Geometry
In recent years randomized incrementation has turned out to be a
highly successful paradigm in computational geometry. There are two
general theories underlying this paradigm: 1) the theory of random sampling
(Clarkson-Shor) and 2) the theory of probabilistic geometric games.
These techniques can be used to analyze the algorithms which are randomized,
and incremental, i.e. to say the algorithms which add objects one at a time
in a random order. Unfortunately, both theories become inapplicable when
deletions of objects are allowed. This happens to be the case when one is
interested in designing fully dynamic algorithms, allowing additions as well
as deletions, for the geometric problems under consideration. Here we shall
extend the theory of probabilistic games to problems involving deletions.
This enables us to design fully dynamic algorithms for several important
goemtric problems and show that they have good expected behaviour. These
problems include:
* Dynamic construction of planar partitions,
* Semi-dynamic hidden surface removal,
* Dynamic construction of Voronoi diagrams in $R^d$,
* Dynamic point location in arrangements of hyperplanes (dimension
three and four),
* Dynamic construction of three dimensional partitions, i.e.
partitions induced by polygons in $R^3$, and dynamic point location
in such paritions,
* Dynamic point location in Voronoi diagrams in $R^2$ and $R^3$.
A crucial ingradient in this extension is a certain Theta-series that can be
associated with abstract combinatorial systems. Previously we had associated
such a series with arrangements of hyperplanes and polytopes in $R^d$ and had
studied semi-dynamic (only additions allowed), random evolutions of geometric
configurations using this series. Now we study fully dynamic, random evolutions.