Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

**
"Applications of allowable sequences to plane geometry"
**

**
Rom Pinchasi, The Hebrew University of Jerusalem**

We shall see some applications of allowable sequences as
presented by Goodman and Pollack to problems concerning finite
sets of points in the plane which are NOT in general position. As an
example: for a finite set *G* of points in the plane and a line *l*spanned by *G* denote by *d*(*G*,*l*) the difference between the number of
points of *G* on the left of *l* and the points of *G* to the right of
*l*. Denote by *d*(*G*) the minimum of *d*(*G*,*l*) over all lines *l* that are
spanned by *G*. Let
*f*(*n*)=*max d*(*G*) where the maximum is taken over all
sets *G* of *n* points in the plane. Then
*f*(*n*)=*O*(*loglog*(*n*)).

Back