McGill - INRIA Workshop on Computational Geometry in Computer Graphics

Bellairs Research Institute of McGill University
February 9 - 15, 2002

Problems & Solutions

  1. 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 collector's problem.

  2. 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. [11]

  3. 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. [11]. 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.

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

  5. What is the expected total size of the shadow boundaries amongst n unit balls? (Hyeon-Suk)

    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. [11]. The lower bound follows from the solution to problem .

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

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

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

  9. 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 HEVEA.