Large Chambers in a Lattice Polygon
(Notes)

## Günter M. Ziegler

### Problem-description

```From: Bernd Sturmfels Tue Oct 10 01:59:15 2000

Dear friends:

here is a open problem in plane geometry whose
answer we very much like to know. Can you help ?

Bernd

-------------------------------------------------------------------------

Let P be a convex lattice polygon in the plane. We draw the line
segments connecting any two lattice points in P. This gives a
subdivision of P into triangles, quadrangles, pentagons, etc...; let
n(P) denote the maximum number of vertices of any convex
polygon in that subdivision of P.

Question: Can n(P) be arbitrarily large ?  Or does there exist
a constant N such that every lattice polygon P satisfies
n(P) <= N?

-------------------------------------------------------------------------
```

### Solution

In his dissertation Tracy Hall [UC Berkeley, 2004] constructs for any n a polygon P with n(P) at least 4n. This shows that n(P) is unbounded.

Moreover, Tracy Hall shows that the shape of any centrally symmetric polygon can be approximated arbitrarily well (up to an affine transformation) by a polygon inside a suitable chamber complex. (The chamber complex is this subdivision defined above.)

### Rectangles

To our knowledge the problem restricted to rectangles is open.

Below we present computations we performed in 2001, where we computed (bounds for) n(P) for rectangles.

Tracy Hall conjectures that n(P) is bounded by c m, where m is the size of the polygon (i.e., number of edges or vertices). This would imply that n(P) is bounded by 4c for rectangles. He also states that c=4 might be possible (this does not contradict our findings below, where we found a rectangle P with n(P) at least 15).

### Remarks

The paper

"Supernormal Vector Configurations" by
Serkan Hosten, Diane Maclagan, and Bernd Sturmfels
Journal of Algebraic Combinatorics, 19, pp. 297-313, 2004; math.CO/0105036.

explains the background for this problem.

### Two examples

The first is a 5 by 5 square. The largest chamber is of size 6, i.e. n(P)=6 in this case. The second example is a 5 by 9 rectangle. Here n(P)=7. The chambers which achieve the bound are colored red.

### Results

In the following table the maximal number of faces in a chamber of the complete subdivision of a lattice rectangle of size m×n (which has area mn, and contains (m+1)(n+1) lattice points, 2(m+n) of them on the boundary) are displayed. The data is computed by the programs planar_graph/max_cells, based on the LEDA library.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 1 3 2 4 4 3 4 4 4 4 4 4 5 5 5 4 5 5 6 6 6 4 5 5 6 6 6 7 4 5 6 6 6 7 7 8 4 5 7 6 7 7 7 7 9 4 5 6 6 7 7 8 8 8 10 4 5 6 6 7 7 8 8 8 7 11 4 5 6 6 7 7 8 8 8 8 8 12 4 5 7 6 7 7 8 7 8 8 8 8 13 4 5 8 6 7 7 8 7 8 8 8 8 8 14 4 5 8 6 7 7 8 8 8 8 8 8 8 8 15 4 5 8 6 7 7 8 8 8 8 8 8 9 9 9 16 4 5 7 6 7 7 8 8 8 8 8 8 9 9 9 9 17 4 5 7 7 8 8 8 8 8 8 8 8 9 9 9 9 9 18 4 5 8 7 8 8 8 8 8 8 8 8 9 9 9 10 10 9 19 4 5 8 7 8 8 8 8 8 9 20 4 5 8 7 8 8 8 9 8 9 21 4 5 8 7 8 8 9 9 8 9 22 4 5 8 7 8 8 9 8 8 9 23 4 5 8 8 8 8 8 8 8 9 24 4 5 8 7 8 8 8 8 8 9 25 4 5 8 8 8 8 9 8 8 10 26 4 5 8 8 8 8 9 8 8 10 27 4 5 8 8 8 8 9 8 8 10 28 4 5 8 8 8 8 9 8 8 29 4 5 8 8 8 8 9 9 9 30 4 5 8 7 8 8 8 9 9 31 4 5 8 8 8 8 8 9 9 32 4 5 8 8 9 9 8 9 9 33 4 5 8 8 8 9 8 9 9 34 4 5 8 8 8 9 9 9 9 35 4 5 8 8 10 10 8 9 9 36 4 5 8 8 8 8 9 9 9 37 4 5 8 8 9 9 9 9 9 38 4 5 8 8 9 9 9 9 9 39 4 5 8 8 9 9 9 9 9 40 4 5 8 8 9 9 9 9 9 45 4 5 8 8 9 9 9 9 9 50 4 5 8 8 10 10 10 9 9 55 4 5 8 8 10 10 10 10 10 60 4 5 8 8 10 10 10 10 9 65 4 5 8 8 10 10 10 10 9

As one sees the function n(P) is not monotone, not even on the diagonal.

The computation times for the biggest rectangles in each column and on the diagonal are about one day on a 333 MHz Sun Ultrasparc computer.

The next table summarizes the results for the n ×n square, where only the middle 1 ×1 square in the lowest strip is computed. This restriction speeds up the computation enormously.

 n 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 4 6 7 6 7 6 6 7 7 8 8 7 7 8 8 8 8 8 8

Here we have the m ×n rectangle and the middle 1 ×1 square in the lower strip of the longer side is computed:

 m\n 45 55 65 75 85 95 105 115 125 135 145 155 165 175 185 195 205 215 225 5 8 10 10 10 10 9 10 12 12 12 12 10 11 10 10 10 10 12 12 6 8 10 10 10 10 9 10 12 12 12 12 10 11 10 10 10 10 12 12 7 8 10 9 10 10 9 10 10 12 12 12 12 14 14 12 12 12 12 12 8 8 9 9 10 9 10 10 10 10 12 12 12 14 14 12 12 12 12 12 9 8 9 8 9 10 10 10 12 11 12 11 10 11 11 12 12 12 14 14 10 8 9 9 9 10 10 10 12 11 12 11 10 11 11 12 12 12 14 14 11 10 10 10 10 10 10 10 10 10 11 11 11 12 12 12 12 12 14 12
 m\n 235 245 255 265 275 285 295 305 315 325 335 345 355 365 375 385 395 405 5 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 6 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 7 12 12 12 12 12 13 12 12 13 13 14 12 14 14 13 14 12 12 8 12 12 12 12 12 13 12 12 13 13 14 12 14 14 13 14 12 12 9 12 14 14 15 12 12 12 12 14 14 14 12 13 14 14 14 14 14 10 12 14 14 15 12 12 12 12 14 14 14 12 13 14 14 14 14 14 11 12 12 12 13 12 13 12 12 14 12 13 12 12 12 13 15 12 12
 m\n 157 159 161 163 165 167 169 171 173 175 177 179 181 183 7 12 12 13 14 14 14 14 14 14 14 14 12 11 12

The next table gives the results for the squares to both sides of the middle square.

 w h x1 y1 x2 y2 n(P) 7 163 0 80 1 81 14 7 163 0 82 1 83 14 7 165 0 81 1 82 14 7 165 0 83 1 84 14 7 167 0 82 1 83 14 7 167 0 84 1 85 14 7 169 0 83 1 84 14 7 169 0 85 1 86 14 7 171 0 84 1 85 13 7 171 0 86 1 87 13

Here w means width, h is height. The next four values (x1,y1,x2,y2) give the coordinates of the square and the last the result.

Current data last updated: 4/05/2001

 Homepages of Günter M. Ziegler and Marc Pfetsch
 Marc Pfetsch updated: 12/13/2004