Newsgroups:     sci.math.research
From:           wpt@math.berkeley.edu (Bill Thurston)
Subject:        Re: Two problems in hyperbolic arrangements
Organization:   U.C. Berkeley Math. Department.
Date:           Fri, 17 Jun 1994 14:12:54 GMT

In article <1994Jun15.130516.15170@midway.uchicago.edu>,
Greg Kuperberg <greg@math.uchicago.edu> wrote:
>Here is a question that I have been asking a number of people lately
>with the suggestion that it's an open problem:
>
>Is there a constant C>0 such that every compact convex body in the
>hyperbolic plane admits a packing with density at least C?
>
>(NB:  Most hyperbolic packings do not have a well-defined packing
>density.  The question pertains to packings with a co-compact or
>co-finite symmetry group, which have a well-defined density after
>passing to the quotient of the group action.  If you like, you can say
>that good hyperbolic packing of C is an arrangement with disjoint
>interiors of isometric copies of C on a complete, finite-area,
>hyperbolic surface.)
>
>Does anyone know whether this problem is actually open?

The answer is no.  A counterexample is the epsilon neighborhood of a
line segment of length L, as epsilon -> 0 and L is say 1/epsilon.  Call
this shape B.  In any packing of copies of B, consider the Voronoi
diagram.

It's not hard to see that for any copy of B, if the Voronoi cell is
compact, the number of Voronoi neighbors is large if epsilon is small:
That's because for any two lines that are distance at least 2 epsilon
apart, the orthogonal projection of one line to the other has length
O(-log(epsilon)); the same goes for their Voronoi interface, which is a
line epsilon distance from either.  The projection is even shorter if
one line segment "sees" another end-on instead of broadside.  Thus,
since each Voronoi neighbor blocks only a relatively short portion of
the perimeter, the number of Voronoi neighbors is large.

Consider any compact surface packed with copies of B.  Construct
the dual cell-division to the Voronoi diagram (the Delaunay triangulation).
The ratio of edges to vertices is large.  This implies the ratio of
Euler characteristic to #vertices = #copies of B is large.  But the
area of B is approximately 2, so the packing efficiency goes to 0.

	Bill Thurston    wpt@math.berkeley.edu