Let be a finite set of points in the plane, X be a subset of S, and z be a point not in S. X is a z-containing set if z is in the interior of the convex hull of X. Also X is a z-avoiding set if z is not contained in the interior of the convex hull of X. Let C(S) and A(S) denote the sets of minimal z-containing and maximal z-avoiding subsets of S.
E. Boros and V. Gurvich raised the following question:
Is it true that |A(S)| is less than or equal to 2d |C(S)| where d is the dimension of the space?
This inequality is obviously true for d = 1.
In this paper we verify the inequality for d = 2 by proving the following stronger result:
Theorem: Let S be a finite set of points in the plane and z a point not in
S. Suppose that z is in the interior of the convex hull of S. Then |A(S)|
less than or equal to 3 |C(S)| + 1. Moreover, the equality holds if and
only if |S| = 4, the convex hull of S is a quadrilateral Q, and z is the
point of intersection of the two diagonals of Q.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-33.ps.gz
DIMACS Home Page