2nd McGill - INRIA Workshop on Computational Geometry in Computer Graphics

Bellairs Research Institute of McGill University
February 8 - 14, 2003

Photos

Problems & Solutions

  1. An ordinary line is a line passing through exactly two points. Give an O(n) time algorithm to find an ordinary line. (Olivier)

    Preliminary report : ordLine.ps  

  2. How many lines are tangent to 4 triangles in 3D? (Sylvain)

    Solution : Lower bound 76, upper bound 120.

  3. How many connected components of lines pass through 4 line segments? (Frank)

    Solution : click here.

  4. Connected components of lines tangent to 3 unit balls.(Xavier)

    Solution : Upper bound is conjectured to be 3. There is an example with 3.

  5. What is the expected number of lines meeting 4 given lines? (Hyeon-Suk)

    Solution : What distribution to use? Any answer will depend on the distribution. Hopefully rigid motion invariant.

  6. How many non occluded line segments tangent to 4 among k polytopes of total complexity n are there?(Olivier)

    Solution : \Omega(n^2k^2). Still open for free lines. The best lower bound is \Omega(n^2+nk^3).

  7. Given n disjoint unit balls in d-dimensional space, how many combinatorially different line transversals for all of them exist? (Otfried)

    Solution : A paper was submitted to ESA 2003 on the subject. Here it is!

  8. How many non occluded line segments are tangent to a terrain of compexity n? (Olivier)

    Solution : \Omega(n^4). So this problem is uninteresting. (This should be a remark in the 4 tangents paper.)

  9. Are there four disjoint unit spheres that admit 12 tangents? If not, what is the maximum number. (Otfried)

    Solution : This problem is mildly related to Problem 7, as the only currently known example that realizes 12 tangents to 4 (intersecting) spheres actually produces all 12 different geometric permutations. The result of Problem 7 implies that if four disjoint spheres exist that permit 12 tangents, some of these tangents have to realize the same geometric permutation of the spheres. I've asked Thorsten Theobald about this, and immediately came up with four unit balls with centers (0,0,0), (3,0,0), (6,1,0), (9,0,1). They have two different tangents, both of which touch the spheres in the same order. My personal feeling is that this cannot happen for 12 tangents, but I have no idea on how to go about proving it.

  10. What are the degenerate configurations of 4 arbitrary possibly intersecting balls? (Frank)

    Solution : The situation for 1 line and 3 balls is known and they are obvious (previous result from Frank and Gabor Megysi).

  11. Find an algorithm to compute the visibility graph of n unit balls. (Xavier)

    Solution : O(n^7) using semi-algebraic set formulation. Even for the question - is the visibility graph the complete graph - we can't do better.

  12. Find a fast and effective algorithm to determine whether 2 balls are tangentially visible. (Hazel)

    Solution : O(n^2logn) for an exact answer. A discretization method is the other possibility. A nice picture, generated by Frank, showing pairs of curves corresponding to mutual tangent lines can be found here.

    This document was translated from LATEX by HEVEA.