\documentstyle[fullpage,11pt]{article}

\begin{document}

\title{Open Problems Posed at the\\
Second Stony Brook Workshop on Computational Geometry\\
October 23-24, 1992}

\author{
Joseph S. B. Mitchell\\
{\small Department of Applied Mathematics and Statistics}\\
{\small State University of New York, Stony Brook, NY 11794-3600} \\
{\small jsbm@ams.sunysb.edu}
\\ \\ \\ 
Steven S. Skiena\\ 
{\small Department of Computer Science}\\
{\small State University of New York, Stony Brook, NY 11794-4400} \\
{\small skiena@sbcs.sunysb.edu}
}

\date{}

\maketitle

\begin{enumerate}

\item
(Mike Goodrich, Johns Hopkins University)

Designing data structures for point location in planar subdivisions is
a well studied problem in computational geometry.  It is well known
that optimal $O( \lg n)$ queries can be supported with optimal $O(n)$
space/preprocessing.  But what is the best possible constant in the
query operation?  The method of Kirkpatrick has a very high constant
(but is very elegant). The method of Lee and Preparata has
a query time of $3\lg n$, but space complexity $O(n\lg n)$. The
algorithms of Edelsbrunner, Guibas, and Stolfi, of Cole, or of Sarnak
and Tarjan have search time $3\lg n$ and $O(n)$ space.  The very
simple method of Dobkin and Lipton (the ``slab'' method) has query
time $2\lg n$, but $O(n^2)$ space.

Is $2 \lg n$ the best query time that can be done with polynomial
space?  Is it achievable with linear space?  The unit cost comparison
operation is testing whether a point lies to the left or right of a
given line.

\item
(Charles Jones, Washington State University)

Consider the visibility graph $VG(P)$ of a polygon $P$.  Let $G'$ be
an induced subgraph of $VG(P)$, which can be realized as the visibility
graph of some polygon $P'$.  Does there always exist a polygon
realizing $VG(P)$ which ``contains'' $P'$?  (replacing edges of $P'$
by polygonal chains)

A partial answer was established during the workshop, by K.~Romanik
and C.~Piatko.  Consider a polygon $P$ with 5 vertices: $P$ is a
square whose top edge is replace by a pair of edges, $(uv,vw)$, that
``tilt'' off to the side in such a way that the vertex $v$ sees only
the vertices $u$ and $w$ of the square.  Let $P'$ be a square.  Then,
under this labeling, $P$ cannot be constructed from $P'$.  However, if
you relabel, then $P$ can be constructed from $P'$.  Thus, the
question of labeling is important.  It would seem that relabeling for
this purpose is somehow connected to cliques since, in some sense,
labelings on cliques are arbitrary.

\item
(Maharaj Mukherjee, Rensselaer Polytechnic Institute)

Consider an ``erector set linkage'' in two dimensions, consisting of
line segments linked together at hinge points.  Suppose we want to
move the linkage, changing angles, in such a way that: we preserve
collinearities, and we are allowed to move edges by at most
$\epsilon$.  Two questions arise:

\begin{itemize}

\item[(i)]
What is the minimal $\epsilon$ needed to embed the linkage on the
integer lattice?  Here, we are allowed to move each edge by at
most~$\epsilon$.

\item[(ii)]
What is the minimal $\epsilon$ needed to embed the linkage, if we
compute $\epsilon$ by adding together all the $\epsilon$'s from
each of the edges?

\end{itemize}

During the workshop, S. Landau (University of Mass.) solved the first
problem, by showing that it is NP-complete, and then gave a
restricted version which can be done in polynomial time.  (The
solution involves a little bit of elementary number theory; contact
her for further details.)


\item
(Marshall Bern, Xerox PARC)

Given a convex polytope $P$, where each face has been triangulated,
can you decide in polynomial time if $P$ can be triangulated without
Steiner points into tetrahedra each of which have a positive volume?

\item
(Chee Yap, NYU)

We are given a tetrahedron $T$ with two of its edges $e,e'$ specified.
These two edges are opposing, i.e., they do not share any common
vertex.  We study the translational motion of $T$ in 3-space.  We are
only interested in two other line segment obstacles, $E,E'$.  We call
the ordered pairs $O=(e,E)$ and $O'=(e',E')$ {\em contacts}.  For any
translation $Z$, we write $T[Z]$ or $e[Z]$ to denote the
position of $T$ or $e$, respectively.  We assume general position.

We say that $Z$ {\em satisfies} $O$ if $e[Z]$ touches $E$ at some
point $p[Z]$ and is locally free at $p[Z]$ (i.e., $E$ does not
penetrate the interior of $T[Z]$ near $p[Z]$).  The set of all
translations $Z$ that satisfy $O$ can be parametrized by a pair of
numbers, $(r,R)$ --- the distance $R$ of the point $p[Z]$ along $E$
and the distance $r$ of the point $p[Z]$ along $e[Z]$.  Thus, $(r,R)$
parametrizes a rectangular region $G$ representing all translations
that satisfy $O$.  The set of all $Z$ corresponding to points in $G$
that satisfy $O'$ is a line segment $L$ in $G$.  For any $Z$ in $L$,
we define four ``canonical motions'' corresponding to a ray emanating
from $Z$ in a horizontal or vertical direction (in the $(r,R)$
parameter space).  We say $O'$ {\em covers} $O$ if for any $Z$ in $L$,
one of these four canonical motions is not free in the sense that $O'$
penetrates $T$ throughout this motion.

\medskip
\noindent{\bf CONJECTURE:} Either $O'$ covers $O$ or $O$ covers $O'$.
\medskip

{\em Remarks:} We are studying contacts between $T$ and a set of
polyhedradral obstacles.  In all other types of pairs of contacts, one
can show the analogous result (that either $O$ covers $O'$ or
vice-versa).  Combined with this conjecture, we should be able to
prove an $O(n^2\alpha(n))$ bound on the complexity of translating a
tetrahedron amidst such obstacles.  Such a result was recently
obtained by Halperin and Yap for translating a box.

\item
(Subhash Suri, Bellcore)

For any set of points in the plane, the minimum matching, spanning
tree, and Hamiltonian cycle are always non-self-intersecting
structures.  What is the computational complexity of the {\em
maximization} version of these problems, {\em subject to the
constraint that structure be non-self-intersecting}?  Subhash
conjectures (and hopes) that these problems are NP-hard; he has
approximation algorithms for them (for matching, getting at least
${2\over \pi}OPT$; for others, getting at least ${1\over 2}OPT$).

\item
(Matt Dickerson, Middlebury College)

Given a set of $n$ points in the plane, what is the complexity of
finding the minimum area star-shaped polygonization of them?  Since
there are only $O(n^4)$ possible kernels, $O(n^5 \lg n)$ is a trivial
upper bound.  It can probably be lowered to $O(n^4)$.  Can you give a
better algorithm?  What can be said about approximation algorithms?

\item
(Torsten Thiele, communicated by Bernd G\"artner, Freie Universit\"at Berlin)

Consider a set $S$ of $n^2$ points forming an $n \times n$ grid.  We
want to map these points into a larger grid (of size $f(n)$-by-$f(n)$)
in such a way that no three image points are collinear, and the order
type of every triple of non-collinear points of $S$ is preserved.  The
motivating application is to remove degeneracies in a given set of
input data.

Because no three points are collinear, $\Omega(n^2)$ is a trivial
lower bound on $f(n)$ (there can be at most 2 points per row in the
new image, so we must have $n^2$ rows at least).  It can be realized
with $f(n)=O(n^3)$. But can this be tightened?

\item
(Joe O'Rourke, Smith College)

The problem concerns motion planning with moveable obstacles.  Imagine
an $n$-by-$m$ room, subdivided into $nm$ unit square blocks.  There is
a robot in the lower left-hand corner who wants to go the upper
right-hand corner of the room.  Unit square obstacles litter the room.
These obstacles can be {\em pushed} (either horizontally or
vertically) by the robot, but not pulled.

What is the complexity of determining if there exists a strategy of
pushing and moving that gets the robot to the goal?  The problem is
PSPACE-complete if we allow a subset of the obstacles to be glued to
the floor.


\end{enumerate}

\end{document}