SoCG'05, open problem 5

[Ovidiu Daescu]

(Koltun's 9 points conjecture)

The answer is negative: there are (3+3+3) configurations of 3 red,
3 green and 3 blue points moving on linear trajectories at common
constant speed for which each trichromatic circle becomes empty.
Unlike Koltun's 2+3+3 configuration given in the open problem,
it seems these configurations are random, i.e. do not have special
structure (maybe some special structure exists in the past/future
along the moving directions). This suggests that increasing the number
of points would give the same answer.

The first configuration (below) was found by Jiayun Chen, a recent
HS graduate working with me this summer. Other configurations were found
by one of my PhD students, James Palmer.
James has made available a verification program at
http://tiger3k.com/~james/trichrome.exe
This program lets you zoom in and out (by clicking with the left and
right mouse buttons) and step forward and back by 1, 10, 100 or 1000 steps.
The actual length of the step is controlled by the data file, in the format:

[# of steps] [red point count] [green point count] [blue point count]
[step size (float)]
[red x] [red y] [red velocity angle]
 ...
[green x] [green y] [green velocity angle]
...
[blue x] [blue y] [blue velocity angle]
...

The angle is between 0 and 360.

It can also be run in "batch" mode from the command line to search for
solutions (randomly).

Fell free to try it to generate more counterexamples, especially for more
points (4+3+3, 4+4+4, etc.).

Jiayun's configuration is:

50 3 3 3
1
-7 2 137
13.5 -6.5 152
-11 -13 24
-18 18 307
6 17.5 260
-3.5 -8.5 301
-9 0 333
12.5 -4 235
6.5 -7.5 90

(Better seen with step size 0.1 instead of 1; the time step can have a
big effect, especially when a circle "flips" its axis:  as it flips,
if the time step is too large you can miss an event where the circle
becomes empty. By making the time step smaller one could get solutions
that would be missed otherwise but then it takes a lot more time to
compute a solution.)

James has run trials with a time step of 0.1 and points randomly distributed
from -14 to 14 in both x and y.  For about 40,000 trials only one randomly
generated scenario has yielded a solution. Plotting the generated solutions
with k empty circles would probably show an exponential curve of sorts
as k is near 27. Thus, trying a similar approach with more points
(4+3+3, 4+4+4, etc.) could be time consuming.

********************************************************************
  Ovidiu Daescu, Assistant Professor
  Department of Computer Science
  University of Texas at Dallas
  Richardson, TX 75083-0688
  Phone : 972-883-4196
  Fax   : 972-883-2349
  E-mail: daescu at utdallas.edu
********************************************************************


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.