Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!ucsd!ucbvax!GEOMETRY.CIMS.NYU.EDU!pollack
From: pollack@GEOMETRY.CIMS.NYU.EDU (Ricky Pollack)
Newsgroups: comp.theory
Subject: Sixteenth Computational Geometry Day
Message-ID: <9101031420.AA19506@GEOMETRY.CIMS.NYU.EDU>
Date: 7 Jan 91 16:46:07 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: Theory-B - TheoryNet Ongoing Seminars and Lectures
              <THEORY-B@NDSUVM1>,
        Ricky Pollack <pollack@geometry.cims.nyu.edu>
Lines: 114


                        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.