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

explains the background for this problem.

Two examples

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