Stabbing line segments Journal Article


Author(s): Edelsbrunner, Herbert; Maurer, Hermann A; Preparata, Franco P; Rosenberg, Arnold L; Welzl, Emo; Wood, Derick
Article Title: Stabbing line segments
Affiliation
Abstract: An algorithm for the geometric problem of determining a line (called a stabbing line) which intersects each ofn given line segments in the plane is presented. As a matter of fact, the algorithm computes a description of all stabbing lines. A purely geometric fact is proved which infers that this description requiresO(n) space to be specified. Our algorithm computes it inO(n logn) time which is optimal in the worst case. Using the description of the stabbing lines, we are able to decide inO(logn) time whether or not a specified line is a stabbing line. Finally, the problem of maintaining the description of all stabbing lines while inserting and deleting line segments is addressed.
Keywords: data structures; computational geometry; elementary geometry; divide-and-conquer; plane-sweep; geometric transform; dynamization
Journal Title: Bit
Volume: 22
Issue 3
ISSN: 0006-3835
Publisher: Springer  
Date Published: 1982-09-01
Start Page: 274
End Page: 281
DOI: 10.1007/BF01934440
Open access: no
IST Austria Authors
Related IST Austria Work