Problems presented at the open-problem session of the
14th Annual ACM Symposium on Computational Geometry
are listed.
- Jack Snoeyink,
University of British Columbia:
-
-
Given a set P of points and a set S of disjoint
line segments in the plane,
does there always exist a spanning tree of P that, when embedded with
straight edges, has the property that no segment in S is cut
by more than two edges?
-
If the weight of an edge of the spanning tree is the
number of segments of S that it crosses,
then does the minimum spanning tree have weight at most 2 |S|?
One can ask the same questions for paths instead of trees.
Note that an affirmative answer for the first problem implies
an affirmative answer for the second.
While a few constructions give spanning trees with
O (|S| log |S|)
weight, the best known lower bound is 2 |S|.
One can assume that the segments of
S induce a triangulation;
in general, the application is to locate many points
in a triangulation by walking along some ``nice'' path.
Disjointness of segments is important; otherwise spanning trees with low
stabbing number give upper and lower bounds of
O(|S|3/2).
-
Vadim
Shapiro, University of Wisconsin:
- Given two smooth real algebraic hypersurfaces S1 and S2 defined by
polynomials of degree at most d that are tangent along the curve
C (i.e., the locus of second order contact is the curve C),
is there a (smooth?) algebraic hypersurface S that is:
-
the zero set of a polynomial of degree at most d/2,
-
contains C, and
-
at each point of C, S meets both S1 and S2 transversally.
If the degree of S must be greater than d/2,
what is the lowest possible degree of S
satisfying the other requirements?
This problem arises in construction of Boolean set
representations for curved polyhedra; the practical algorithms for
constructing such surfaces are of particular interest.
More details are in [SV].
- [SV]
- V. Shapiro and D. L. Vossler,
Separation for boundary to CSG conversion,
ACM Transactions on Graphics
12 (1993), 35-55.
- Joseph O'Rourke,
Smith College:
- The cover of
Gödel, Escher, Bach (by D. R. Hofstadter)
shows a solid piece of carved wood, which casts the letters
G E B
as shadows in three orthogonal directions.
This suggests two questions:
-
Are there simple conditions on three shapes to be
realizable as shadows of a single, connected solid object
in 3-space?
An example of realizable shapes is shown in Figure 1.
An example of unrealizable shapes is provided by the three letters
X X O.
Are there any interesting classes of shapes such that any
three in the class are mutually realizable?
-
Extend this question to d dimensions.
For example, can the letters
J O S E P H be realized as the six 2-dimensional
shadows of a 4-dimensional object?
|
Figure 1:
An orthogonal polyhedron whose shadow in each of the three
labeled directions is an orthogonally polygonal letter of the alphabet.
Fig. 4.22 in [OR].
- [OR]
- J. O'Rourke, Computational Geometry in C (Second Edition),
Cambridge University Press, Cambridge, 1998.
-
Micha Sharir,
Tel Aviv University:
- Let S be a set of n points in the plane, each moving with
a fixed velocity.
How many times does the combinatorial
structure of the Euclidean Voronoi diagram of S change over time?
The best known lower bound is quadratic, and the best known
upper bound is cubic; see [SA, Sec. 8.6.3]. If the distance is measured in
the L1-metric, then the structure of the Voronoi diagram
changes only O(n2a(n))
times [Ch], where a(·) is the inverse Ackermann function.
- [Ch]
- L. P. Chew, Near-quadratic bounds for the L1 Voronoi diagram
of moving points, Proc. 5th Canad. Conf. Comput.
Geom. , 1993, pp. 364-369.
- [SA]
- M. Sharir and P. K. Agarwal, Davenport-Schinzel
Sequences and Their Geometric Applications,
Cambridge University Press, New York, NY, 1995.
-
Subhash Suri,
Washington University:
- Let S be a set of n points in the plane. For a given
point c in the plane, the star of
S is the set of edges
{cp | p in S}. The weight of
a star is the sum of the lengths of its edges. Let MS (S)
denote the minimum-weight star of S, where the minimum is
taken over all points in the plane, and let MWT (S)
denote the maximum-weight Euclidean matching of S.
Obtain an upper bound on the ratio MS (S)/MWT (S).
It can be proved that MS (S)/MWT (S)
< 2,
but the conjecture
is that the ratio is bounded by . The latter bound
can be achieved by many examples.
This problem arises in analyzing the performance of a
network design heuristic. MS(S) and MWT(S) provide upper
and lower bounds, respectively, on the cost of traffic handling.
See [FST] for details.
- [FST]
- A. Fingerhut, S. Suri, and J. S. Turner,
Designing minimum cost nonblocking communication networks,
J. Algorithms 24 (1997), 287-309.
-
John Sullivan, University of Illinois:
- A knot K in R3
can be represented by its projection on
the xy-plane. The xy-projection is a self-intersecting
curve K*. At each such intersection point of K*,
we describe which of the two corresponding portions of K lies
above in the z-direction.
Given such a combinatorial description of a knot K with n
intersection points in K*, what is the minimum
length of a rope of width 1 that can realize K.
Some knots may require the length of the rope to be , but is this an upper bound?
It can be achieved with O(n2).
-
Julien Basch,
Stanford University:
- Let S be a set of n segments in the plane. For a given
x-coordinate t, let lt
be the line x=t, and let
be the set of segments intersected
by the line lt. Suppose we construct a heap on
St, using the y-coordinates of the intersection points
of St with
lt as the keys. We maintain this heap as the
value of t varies continuously from to .
That is, whenever lt passes through an endpoint,
the associated segment
is inserted into or deleted from the heap in the usual way, and
when lt passes an intersection point between two
segments p,q in St
so that p
is the parent of q, the two elements are swapped to maintain
the heap property.
Obtain an upper bound on the number of swaps required
to maintain the heap.
If S is a set of lines, the best known upper bound on the
number of swaps is
O(n log2 n).
For segments, the best known upper bound is
O(n3/2log n);[BGR].
- [BGR]
- J. Basch, L. Guibas, and G. Ramkumar,
Sweeping lines and line segments with a heap,
Proc. 13th Annu. ACM Symp. Comput. Geom. , 1997, pp. 469-472.
-
Victor Milenkovic,
University of Miami:
- Let P be a simple polygon in the plane. Let o be a
reference point in P, which coincides with the origin in the
standard placement of P. Let be a ray emanting from
o attached to P. Let denote the placement of
P at which o lies at the origin and the angle between the
and the x-axis is .
Given a function ,
where , define
Given , find a function so that the
area of is maximized.
Can be computed efficiently?
What if we impose certain restrictions on ? For
example, can be restricted to be rotation with
respect to a point in P.
This problem arises in packing a family of polygons inside
another polygon; see [Mi].
- [Mi]
- V. J. Milenkovic,
Rotational polygon containment and minimum enclosure,
Proc. 14th Annual ACM Symp. Comput. Geom. , 1998, 1-8.
-
Joseph Mitchell,
SUNY Stony Brook:
- Let S be a set of points in convex position in
R3. Can the convex hull of
S always be triangulated
(partitioned into tetrahedra)
so that the
dual graph of the triangulation has a Hamiltonian path?
The same question applies to points in convex position in
Rd, d > 4.
It is obviously true for points in convex position in the
plane.
Once such a triangulation is given for points in convex
position, then points can be added in the interior of the convex hull
and can be triangulated so that the new triangulation also
admits a Hamiltonian path. See [AHMS].
- [AHMS]
- E.M. Arkin, M. Held, J.S.B. Mitchell, and S.S. Skiena,
Hamiltonian triangulations for fast rendering, The
Visual Computer 12 (1996), 429-444.
-
Steve
Vavasis, Cornell University:
- Let P be a polyhedron in
R3, and let be a
simplicial complex.
Can one check in near linear time whether is a valid
mesh for P, that is, whether the simplices in have
disjoint interiors and their union is P?
- Jack Snoeyink,
University of British Columbia:
- Let S be a set of n x-monotone arcs with a total of k
intersection points. Every pair in S intersects at
most once. The following two operations are allowed on
S:
- (i)
- Given an arc, return its left and right endpoints.
- (ii)
- Given an endpoint p of an arc and another arc
s, determine whether p lies above or below
s,or whether the x-projections of p and
s are disjoint.
Using these primitives, how fast can one report all pairs of
intersecting arcs in S?
No subquadratic algorithm is known.
An lower bound is not difficult to prove.
Is there an algorithm that achieves this complexity?
A related question is how fast can one find a maximal set of
nonintersecting arcs.
This problem arises in developing an efficient, robust algorithm
for computing the intersection points of segments.
- [BS]
- J.-D. Boissonnat and J Snoeyink,
Efficient
algorithms for line and curve segment intersection
using restricted predicates, in preparation.
-
Herbert Edelsbrunner,
University of Illinois:
- Let S be the set of vertices of a strictly convex n-gon in
R2. Let u(S) be the number of pairs of vertices p, q in s
at distance 1 from each other.
Prove or disprove that u(S) = O(n).
Füredi [Fu] proved that that
u(S) = O(n log n), and
Edelsbrunner and Hajnal [EH] proved that there are strictly convex
n-gons in the plane for which
u(S) > 2n-7.
- [EH]
- H. Edelsbrunner and P. Hajnal, A lower bound on the number of
unit distances between the vertices of a convex polygon,
J. Combin. Theory Ser. A 56 (1991), 312-316.
- [Fu]
- Z. Füredi, The maximum number of unit distances in a
convex n-gon, J. Combin. Theory Ser. A 55 (1990), 316-320.
-
Herbert Edelsbrunner,
University of Illinois:
- An unfolding of the boundary of a convex polytope P is a
polygon obtained by cutting a tree on the surface that spans the
vertices. The resulting flattened polygon has no polytope vertices
in its interior, and all interior ``fold lines,'' i.e., polytope edges,
leave no trace in the polygon.
However, we retain the gluing pattern by recording which pairs of
polygon edges were generated by a surface cut. See Figure 2.
Figure 2:
Unfolding of a tetrahedron.
|
Alexandrov [A] showed that if the total angle is at most at every
vertex and the gluing pattern results in a region homeomorphic to
S2,then the polygon is an unfolding of a unique convex polytope.
Give an algorithm that constructs the convex polytope from
the polygon.
- [A]
- A. D. Aleksandrov, Konvexe Polyeder, Akademie Verlag, Berlin, 1958.
-
Joseph Mitchell,
SUNY Stony Brook:
- Let S be a set of points in the plane so that the diameter
of S is at most 2.
Is there a unit radius circle that
passes through exactly two points of S
(an ordinary circle)?
The classic result of Sylvester shows that for n points in
the plane, not all on a common line, there exists an ordinary
line (a line through exactly two points). See [BM, CS] for a
summary of known results on this problem.
This question about unit
circles
[A. Bezdek, personal comm.]
is a natural generalization.
If diameter of S is at most , then there is always
such a unit circle.
- [BM]
- P. Borwein and W. Moser, A survey of Sylvester's problem and
its generalizations,
Aequationes Mathematicae 40 (1990), 111-135.
- [CS]
- J. Csima and E. T. Sawyer,
The 6n/13 theorem revisited,
Graph Theory, combinatorics and Applications:
Proc. 7th Quadrennial Intl. Conf. Theory and
Appls. of Graphs, vol. 1, (Y. Alavi and A. Schwenk, eds.), John Wiley
and Sons, Inc. 1995, pp. 235-249.
-
Pankaj K. Agarwal,
Duke University:
- Let S be a set of segments in the plane. Suppose S
contains a subset A of k pairwise disjoint segments.
Describe a polynomial-time algorithm to find a
large subset of pairwise disjoint segments of S.
A few approximation algorithms are described in [AKS,DMMMZ] if S is
a set of orthogonal rectangles or circles.
- [AKS]
- P. K. Agarwal, M. van Kreveld, and S. Suri,
Label placement by maximum independent set in rectangles,
to appear in Comput. Geom.: Theory and Appls.
- [DMMMZ]
- S. Doddi, M. Marathe, A. Mirzaian, B. Moret, and B. Zhu,
Map labeling and its generalization,
Proc. 8th ACM-SIAM Sympos. Discrete Algorithms, pp. 148-157, 1997.