pollack@geometry.cims.nyu.EDU (Ricky Pollack) (04/30/91)
SEVENTEENTH COMPUTATIONAL GEOMETRY DAY
Friday, May 24, 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 Michael T. Goodrich, Johns Hopkins University
Dynamic Trees and Dynamic Point Location
11:30-12:15 Imre B\'ar\'any, Courant Institute, Hungarian Academy
of Sciences and Yale University
Halving Hyperplanes in $d$-space and a Colored Version of
Tverberg's Theorem
12:30-2:00 - Lunch
2:00-3:00 Open Problem Session
3:00-3:45 Micha Sharir, Courant Institute and Tel Aviv University
Complexity in Arrangements: Recent Developments with Simple Proofs
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
**************************Abstracts******************************************
Dynamic Trees and Dynamic Point Location
Michael T. Goodrich, Johns Hopkins University
We give new methods for maintaining a point-location data structure for a
dynamically-changing monotone subdivision S. Our approach is based on
a new, optimal static point-location structure, where one represents S
via two interlaced spanning trees, one for S and one for the
graph-theoretic dual of S. Queries are answered by using a centroid
decomposition of the dual tree to drive searches in the primal tree.
We maintain these trees via the link-cut trees structure of Sleator
and Tarjan, leading to a scheme that achieves vertex insertion/deletion
in O(log n) time, insertion/deletion of k-edge monotone chains in
O(log n + k) time, and answers queries in O(log^2 n) time, with O(n)
space.
Our techniques also allow for the dual operations {\it expand} and
{\it contract} to be implemented in O(log n) time, leading to an improved
method for spatial point-location in a 3-dimensional subdivision.
In addition, we apply our approach to on-line point-location
(where one builds S incrementally), improving our query bound to
O(log n*loglog n) time and our update bounds to O(1) amortized time,
in this case. We believe this is the first on-line method to achieve a
polylogarithmic query time and constant update time.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Halving Hyperplanes in $d$-space and a Colored version of
Tverberg's Theorem
Imre B\'ar\'any, Courant Institute, Hungarian Academy of Sciences
and Yale University
Let $n$ points be given in $d$-space in general position. Any $d$ of them
determine a halving hyperplane if the hyperplane spanned by these $d$
points exactly bisect the remaining $n-d$ points. So the number of
halving hyperplanes is at most $n\choose d$. A recent result of
\u{Z}ivaljevi\'{c} and Vre\'{c}ica implies that the number of halving
hyperplanes is $O(n^{d-\epsilon _d})$ where $\epsilon _d = (4d)^{-(d+1)}$.
For $d=2$ and $d=3$ better results are known but this is the first
$o(n^d)$ bound for $d>3$. The result of \u{Z}ivaljevi\'{c} and Vre\'{c}ica
is a colored version of Tverberg's theorem. Namely, given sets $C_1,
\dots , C_{d+1} \subset \bf R^d$ of cardinality $4r$ each, there exist
pairwise disjoint sets $S_1, \ldots ,S_r$ of cardinality $d+1$ each such
that $|C_i \cap S_j|=1$ $(\forall i,j)$ and $\cap _{j=1}^r
\mbox{conv}(S_j)$
is nonempty.
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Complexity in Arrangements: Recent Developments with Simple Proofs
Micha Sharir, Courant Institute and Tel Aviv University
About half a year ago, a new proof of the ``Zone Theorem''
was found by Edelsbrunner, Seidel and Sharir, after an error in the
old proof was found. The new proof is based on a very simple inductive
technique. Since then, this technique has been extended to obtain many
new results on complexity in arrangements, whose proofs are all
fairly simple. These results include sharp bounds on
(i) the sum of squares of cell complexities in hyperplane arrangements;
(ii) the complexity of the zone of an algebraic or convex surface
in a hyperplane arrangements;
(iii) the complexity of a single cell in an arrangement of (d-1)-simplices
in d-space.
In the talk, we present these results, describe the new proof
technique, and explain some of the specific proofs.
(Joint work with B. Aronov, H. Edelsbrunner, J. Matou\v{s}ek and
R. Seidel.)