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 Székely'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)


For more information contact: Richard Pollack (212) 998-3167
                              pollack@geometry.nyu.edu


*********************************abstracts*******************************

                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).



        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.


                        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.