Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
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 lspanned 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
