McGill - INRIA Workshop on Computational Geometry in
Bellairs Research Institute of McGill University
February 9 - 15, 2002
Problems & Solutions
- Find an algorithm with low expected running time to compute
the visibility events amongst n unit balls uniformly distributed in a universal
ball . (Helmut and Sylvain)
Solution : There is an algorithm with expected running time O(nlog n)
that finds most of the visibility events with high probability. See the coupon
Show a lower bound on the expected number of visibility events amongst n unit
balls. (Helmut and Sylvain)
Solution : Omega(n). The idea is to start with the example by Macdonald,
Pach and Theobald of 4 balls admitting 12 real common tangents, which is the maximum
possible. The centers of these balls can be perturbed within an epsilon neighborhood
while keeping 12 tangents. Given two balls such that the distance between their
centers lies in a specific given range computed from the example, there will
necessarily exist a tangent (12, in fact) to these and two additional balls if the
centers of the two additional balls lie within a certain epsilon neighborhood of
specified points, computed from the example, in the cylinder determined by the first
two balls. Now imitate the integral in the proof of the upper bound in Devillers et al. 
What is the expected number of visibility events amongst n unit balls such that each of
the centers lies in a given ball of radius e with a uniform distrubition. In other words,
are the peaks of high complexity local? (Hazel)
Partial solution : If e is small, the expected number of visibility events might
be Omega(n2) : take the Omega(n2) worst-case example and e-balls
around all the centers, with e very small.
When e is very big, say R, the expected number of visibility events is linear by Devillers et
al. . The question is thus: is there a constant e big enough for which the expected
number of visibility events is linear for any position of the e-balls.
Prove or disprove that the set of lines tangent to 3 unit balls is connected. (Xavier)
Solution : This isn't true. The number of connected components seems to be
related to the number of geometric permutations. It is known that n disjoint unit
balls admit at most 4 geometric permutations. It is conjectured that for n > 3,
there are only 2 geometric permutations. Three unit balls whose centers form an
equilateral triangle of side length a little bigger than 2 admit three distinct
geometric permutations. For each of these permutations there is a tangent that meets the three
balls in that order. Such a tangent cannot be continuously moved to a tangent
corresponding to a different permutation while staying tangent to the three balls.
What is the expected total size of the shadow boundaries amongst n unit balls?
Solution : Q(n). The idea is to consider a vertex of the arrangement of
the shadows on a ball a. This vertex is the intersection of two curves, one
determined by the T3 surface generated by balls i, j and k and the other
determined by the T3 surface generated by balls l, m and n. We compute the
probability that i and j are in the cylinder determined by a and k and the
line segment passing through the vertex and tangent to the three balls i, j and
k is not occluded. Similarly for l, m and n. Proceed as in the upper bound
proof in Devillers et al. . The lower bound follows from the solution to problem
How many visibility events can there be among 4 convex polyhedra with a
total of n vertices ? (Hervé and Sue)
This question can also be asked for k convex polyhedra with a total of n vertices. We are
interested in bounds in the worst case. The expected case is the purpose of the next question.
What happens if the spheres enclosing the polyhedra are disjoint?
Solution : There are at most O(n2) non-occluded line segments tangent to 4 polyhedra with
a total of n vertices. Actually the complexity is a O of n times the worse size complexity of
the silhouette of one of the 4 polyedra (Xavier and Sue). There are at most O(n2k2) non-occluded
line segments tangent to k polyhedra with a total of n vertices. Similarly as before, the
complexity is a O of nk2 times the worse size complexity of the silhouette of any of the k
polytopes. There are examples showing lower bounds of Omega(n) and Omega(k4).
Find a set of conditions on a convex polyhedron on n vertices such that the number of
visibility events is O(n . sqrt(n)). (Xavier and Marc and Helmut)
It suffices to find conditions such that the silhouette of the polyhedron has size O(sqrt(n)).
There is an example of a polyhedron with the following properties that has a linear sized
silhouette : ratio of longest segment to the shortest segment is bounded, the
polyhedron has bounded aspect ratio.
What is the expected number of visibility events amongst n convex polyhedra?
(Hervé, Sylvain and Vida)
The question can be asked for various polyhedra, for instance triangles whose reference point and
orientation are uniformly distributed in the sphere. Another observation that might turn out to be
useful is the Löwner-John pair of ellipsoids: the theorem says that any convex polyhedron can
be inscribed in an ellipsoid that has radius at most 3 times that of the largest ellipsoid that
can be inscibed in it. Can the proof idea for spheres work for ellipsoids ?
Partial solution : The expected bound is O(n) for unit line segments in the plane, and
congruent triangles in space (uniformly distributed in position and orientation) if the boundary
cases can be dealt with. If the triangles are distributed on the boundary of at most k convex
polyhedra containing a ball whose radius is a constant time that of its enclosing ball, each with
n/k triangles, then the
bound on balls apply and combined with the bound on four polyhedra, give O(k) times
O((n/k)2), namely O(n2/k). General case still open.
Given a square and a set of segments inside the square and a target cost. Can you find a
quadtree that realizes this target cost ? Is this NP-complete ? The cost function for a
quadtree is the following : SUMc(1 + nc)l(c) where c is a cell of the quadtree,
nc is the number of segment pieces in cell c and l(c) is the perimeter of cell c.
(David and Marc)
A related question is whether there is an approximation algorithm based on a greedy algorithm
that requires a fixed amount of look ahead. The ultimate question involves triangles in 3D, and a
cost measure on the octree which is SUMc(1 + nc)s(c), where s(c) is the surface
area of an octree cell.
Partial solution: The lookahead required to know if the quadtree is optimal can be infinite
for segments. In the case of points (a point may be in four, three, two, or one cell), the
conjecture is that lookahead 4 suffices, or phrased differently ``is not subdividing a quadtree
optimal (at a cost 1+nc) if no quadtree of depth at most 4 has a lower cost?'' For segments, it
still makes sense to ask about an approximation algorithm:
if subdividing a constant number of more levels does not bring cost improvements, is the cost of the
quadtree within some constant of the optimum?
This document was translated from LATEX by