An almost optimal bound on the number of intersections of two simple polygons

Abstract: What is the maximum number of intersections of the boundaries of a simple

m

-gon and a simple

n

-gon, assuming general position? This is a basic question in combinatorial geometry, and the answer is easy if at least one of

m

and

n

is even: If both

m

and

n

are even, then every pair of sides may cross and so the answer is

m n

. If exactly one polygon, say the

n

-gon, has an odd number of sides, it can intersect each side of the

m

-gon at most

n - 1

times; hence there are at most

m n - m

intersections. It is not hard to construct examples that meet these bounds. If both

m

and

n

are odd, the best known construction has

m n - (m + n) + 3

intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only

m n - (m + l c e i l f r a c n 6 c e i l)

, for

m g e n

. We prove a new upper bound of

m n - (m + n) + C

for some constant

C

, which is optimal apart from the value of

C

.

Recommendations

Cites Work

Cited In (7)

This page was built for publication: An almost optimal bound on the number of intersections of two simple polygons