New York University

Courant Institute of Mathematical Sciences

TWENTY SIXTH COMPUTATIONAL GEOMETRY DAY

Friday, April 26, 1996 Room 109, Warren Weaver Hall 251 Mercer St., New York, NY 10012

10.00--10.30 Coffee (Warren Weaver Hall Lobby)

10:30--11:15 Janos Pach, CUNY and Courant Institute Counting Unit Distances -- the Advantages and Limitations of Szekely's Method

11:30--12:15 Joseph O'Rourke and Ileana Streinu, Smith College Pseudo-visibility Graphs in Pseudo-polygons

12:30--2:00 Lunch

2:00--3:00 Open Problem Session

3:00--3:45 John Canny, UC Berkeley Fun with Duality

4:00--5:00 Wine and Cheese Reception (13th floor lounge)

Counting Unit Distances -- the Advantages and Limitations of Szekely's Method

Janos Pach

What is the maximum number of times that the unit distance can occur among $n$ points in the plane? This innocent looking question of Erdos, raised in the American Mathematical Monthly fifty years ago, has generated a lot of research in combinatorial geometry and in extremal graph theory. The best known upper bound, $O(n^{4/3}$ is due to Spencer, Szemeredi, and Trotter, but it is widely conjectured that the asymptotically optimal configuration is a square grid which realizes the unit distance $\Theta(n^{1+c\log\log n})$ times. Recently, Laszlo Szekely (Budapest) has discovered a very elegant argument for proving the $O(n^{4/3})$ bound, based on a simple topological lemma of Ajtai-Chvatal-Newborn-Szemeredi and Leighton. This lemma states that in any drawing of a graph with $v$ vertices and $e\geq 4v$ edges, there are at least $\frac{1}{64}\frac{e^3}{v^2}$ crossing pairs of edges. After presenting Szekely's proof, we deduce some of its consequences, and discuss related results. Some of the results were obtained jointly with Sharir and Toth.

Pseudo-Visibility Graphs in Pseudo-Polygons

Joseph O'Rourke and Ileana Streinu

We extend the notion of polygon visibility graphs to pseudo-polygons defined on generalized configurations of points.'' Removal of the condition that lines-of-sight be straight widens the class of graphs obtained. We also introduce a new type of polygon visibility graph, the vertex-edge visibility graph, which we show encodes stricly more information about the (pseudo-)polygon than does the vertex visibility graph. We study the reconstruction problem for vertex-edge pseudo-visibility graphs. Given a bipartite graph $G$ satisfying certain properties, which can all be checked in polynomial time, we show that we can define a generalized configuration of points and a pseudo-polygon on it, so that its vertex-edge pseudo-visibility graph is $G$. This provides a full characterization of vertex-edge pseudo-visibility graphs and a polynomial-time algorithm for the decision problem. It also implies that the decision problem for vertex visibility graphs of pseudo-polygons is in NP (as opposed to the same problem with straight-edge visibility, which is only known to be in PSPACE).

Fun with Duality

John Canny

Duality lets us solve only half the computational geometry problems, and the other half come for free. In '91 Ming Lin and I published an algorithm for computing distance between convex polyhedra which verifies closest points in constant time, and tracks closest points in constant time empirically. The algorithm couldnt deal with overlapping polyhedra. Using duals, we reduce overlap to distance, and compute penetration depth also in constant empirical time. Recently, we looked at the problem of sensor placement for tightest possible pose estimation. Here an object's pose is already known approximately, but must be refined for a task. This problem is very common in manufacturing, probably more common than sensing with unknown initial pose. But it has not received much attention. Through duality, optimal sensor placement corresponds to optimal finger placement for stable grasping.