pollack@GEOMETRY.CIMS.NYU.EDU (Ricky Pollack) (10/25/90)
FIFTEENTH COMPUTATIONAL GEOMETRY DAY
Friday, November 9, 1988
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
We will present a divide-and-conquer strategy for triangulating
a simple polygon efficiently. The algorithm is deterministic
and runs in time $O(nlog^*n)$, where n is the number of vertices.
The same method can also be used to check whether a polygonal curve
is simple.
*****************************************************************************
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.