## DIMACS TR: 2002-33

## On Convex Polytopes in the Plane "Containing" and "Avoiding" Zero

### Authors: R. Collado, A. Kelmans and D. Krasner

**
ABSTRACT
**

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