Points and Lines in the Plane
Justin W. Smith · OhioLink ETD Center (Ohio Library and Information Network) · 2010
This thesis will focus on two topics: (1) finding intersections determined by an arrangement of hyperplanes (e.g., lines in a plane), and (2) lower bounds on the number of various "types" of lines determined by a configuration of points.The first topic is algorthmic.Given an arrangement of n lines in R 2 , a O(n log n) algorithm is demonstrated for finding an ordinary intersection (i.e., an intersection of exactly two lines).This algorithm is then extended to finding an ordinary intersection among hyperplanes in R d , under the hypothesis that no d hyperplanes pass through a line and not all pass through the same point.Algorithms are also given to find an ordinary intersection in an arrangement of pseudolines in time O(n 2 ), and to find a monochromatic intersection in a bichromatic arrangement of pseudolines in time O(n 2 ).The second topic is combinatorial.Let G and R be finite sets of points, colored green and red respectively, such that |G| = n, |R| = n -k, G ∩ R = ∅, and G ∪ R are not all collinear.Lower bounds will be demonstrated for several types of lines (e.g., bichromatic and equichromatic) determined by few points in R 2 . List of Tables 5.1Best General Lower Bounds . . . . . . . . . .