From:           piatko@svax.cs.cornell.edu (Christine Piatko)
Newsgroups:     comp.theory
Subject:        Re: geometry problem
Date:           6 Mar 90 17:14:17 GMT
Organization:   Cornell Univ. CS Dept, Ithaca NY

In article <9002132315.AA01951@rhmr.com> Richard Schroeppel <rcs%la.tis.com@VM1.NoDak.EDU> writes:
>Suppose you have a planar polygon, not necessarily convex.
>The interior face of each edge is a mirror.
>A candle is lighted at some interior point.  The light spreads
>out, reflects off the mirror edges and spreads further, etc.
>Is any place inside the polygon completely dark?
>
>Rich Schroeppel
>rcs@la.tis.com

As far as I know, this is still an open problem.  This problem is stated
on p. 265-6 of Joseph O'Rourke's book "Art Gallery Theorems and Algorithms."
He states "The original poser of the problem is unknown; Klee 
popularized the problem in two articles" (which are:
"Is every polygonal region illuminable from some point?"
          Amer. Math. Monthly 76 (1969), 180.
"Some unsolved problems in plane geometry," 
          Math. Mag. 52 (1979), 131-145.).
 
For those of you without access to O'Rourke's book, here are the precise
problems, and what is known about them:

"Let P be a polygon and imagine that all of its edges are perfect mirrors.
Is there always at least one interior point from which P is completely 
illuminable by a point light bulb?  Is P always illuminable from
_each_ of its points?  Assume that the light bulb sends out rays in all
directions, and that the standard 'angle of reflection = angle of
incidence' law of reflection holds.  Further assume that a light ray is 
absorbed if it hits a vertex.  Surprisingly, these problems are unsolved for
polygons. However, Klee showed the answers to be 'no' if curved
(differentiable) arcs are permitted."  

(In the book are two figures with curved arcs.  One shows a region that
is not illuminable from a point x, but is illuminable from another point y.
Basically x is at the center of 2 semicircles, the upper one having a
larger radius than the lower one and there are some bays between the
two arcs.  You can use your imagination to reconstruct it from the following:
                .---------------------.   
               /           y           \ <== top circular arc
               |                       |
               |                       |
               |                       |
                \_ _/|     x     |\_ _/  <== bay
                     |           |
                      \_________/   <== bottom circular arc

The other shows a region that is not illuminable from any of its points.
There are two elliptical arcs with foci (a,b) and (a',b') and some bays.
Any light source above the a'b' major axis will not illuminate regions
A' or B', and similarly for below the ab axis.  And a light source in A
will bounce into B and back again, never illuminating A' or B'.
You can use your imagination to reconstruct it from the following:
                .--------------------------.   
               /                            \ <== top elliptical arc
               |                            |
               |                            |
               |         a       b          |
                \___A___/\       /\___B____/  <== bays
                          |     |
                          |     |
                 _______  |     |  ________   
                /   A'  \/       \/   B'   \  <== bays
               |         a'      b'         |
               |                            |
               |                            |
               \                            / <== bottom elliptical arc
                \__________________________/   
).

O'Rourke goes on to say:

"Although the problem remains unsolved for polygonal regions, some progress
has been made in understanding the behavior of single light rays in a
_rational_ polygon, one whose angles are all rational multiples of $\Pi$.
(Orthogonal polygons are a very special case of rational polygons.)  A
single light ray is more usually called a "billiard ball" in the now rather
substantial literature on the subject...

Theorem 10.4 [Boldrighini et al. 1978' Kerckhoff et al. 1985].  Let x be
a point in a rational polygon P and $\Theta$ a direction.  Then, except
for a countable number of "exceptional" directions $\Theta$, the path of
a billiard ball issuing from x in the direction $\Theta$ is spatially dense
in P, that is, passes arbitrarily lose to every point of P.

One implication of this result is that every rational polygon is 
illuminable from each of its points in the sense that no finite area
region will be left unilluminated;  whether an isolated point could remain
in the dark is unclear.

For irrational polygons, almost nothing is known.  It is not even known 
if every triangle admits a dense billiard path."

C. Boldrighini, M. Keane, and F. Marchetti, "Billiards in polygons,"
   Ann. Prob. 6 (1978), 532-540.
S. Kerckhoff, H. Masur, and J. Smillie, "A rational billiard flow is 
   uniquely ergodic in almost every direction," 
   Bull. AMS 13 (1985), 141-142.
Christine (piatko@cs.cornell.edu)