2nd McGill - INRIA Workshop on Computational Geometry in
Bellairs Research Institute of McGill University
February 8 - 14, 2003
Problems & Solutions
An ordinary line is a line passing through exactly two points. Give an
O(n) time algorithm to find an ordinary line.
Preliminary report :
How many lines are tangent to 4 triangles in 3D? (Sylvain)
Lower bound 76, upper bound 120.
How many connected components of lines pass through 4 line segments?
Connected components of lines tangent to 3 unit balls.(Xavier)
Upper bound is conjectured to be 3. There is an example with 3.
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.
How many non occluded line segments tangent to 4 among k polytopes of
total complexity n are there?(Olivier)
\Omega(n^2k^2). Still open for free lines. The best lower bound is
Given n disjoint unit balls in d-dimensional space, how many
combinatorially different line transversals for all of them exist?
A paper was submitted to ESA 2003 on
the subject. Here it is!
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.)
Are there four disjoint unit spheres that admit 12 tangents? If not,
what is the maximum number.
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.
What are the degenerate configurations of 4 arbitrary possibly
Solution : The situation for 1 line and 3 balls is known and they
are obvious (previous result from Frank and Gabor Megysi).
Find an algorithm to compute the visibility graph of n unit balls.
O(n^7) using semi-algebraic set formulation. Even for the question - is the
visibility graph the complete graph - we can't do better.
Find a fast and effective algorithm to determine whether 2 balls are
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