2nd McGill  INRIA Workshop on Computational Geometry in
Computer Graphics
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.
(Olivier)
Preliminary report :
ordLine.ps

How many lines are tangent to 4 triangles in 3D? (Sylvain)
Solution :
Lower bound 76, upper bound 120.

How many connected components of lines pass through 4 line segments?
(Frank)
Solution :
click here.

Connected components of lines tangent to 3 unit balls.(Xavier)
Solution :
Upper bound is conjectured to be 3. There is an example with 3.

What is the expected number of lines meeting 4 given lines? (HyeonSuk)
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)
Solution :
\Omega(n^2k^2). Still open for free lines. The best lower bound is
\Omega(n^2+nk^3).

Given n disjoint unit balls in ddimensional 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!

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

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

Find an algorithm to compute the visibility graph of n unit balls.
(Xavier)
Solution :
O(n^7) using semialgebraic 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
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 L^{A}T_{E}X by
H^{E}V^{E}A.