Problems in discrete geometry
Márió Szegedy, Vašek Chvátal, Xiaohong Chen · 2006
The Sylvester-Gallai theorem asserts that any non-collinear point set in the plane determines a line passing through exactly two points in the set. The problem was posed by Sylvester in 1893 and first solved by Gallai in 1930s. Many proof were found, including the surprisingly short proof of Kelly using Euclidean distances, and the one by Melchoir using Euler's formula. We survey the history of the theorem and related problems, including various proofs of the classical Sylvester-Gallai theorem, the lower bound on the number of Gallai lines, the deBruijn-Erdohs theorem, the Scott's conjecture and Ungar's theorem, the Dirac conjecture, the magic configuration conjecture, the question on the number of Gallai points, and the colored version of the problem. We then present the recent work on the generalization of these problems in arbitrary metric space and hypergraphs. In particular, we present the Sylvester-Chvatal theorem and the problems related to the de Bruijn-Erdohs theorem. Another problem we study in this dissertation is the visibility of points and segments in the plane. We color the end points of each segments red and blue, and study, in particular, the visibility relations between the red points and the blue ones. We introduce the general frame work of the problem, and prove two main theorems about the visibility graph.