Finding degeneracies among sets of lines Original Research Article

Suppose there are k sets each containing n lines in the plane. One might be interested in locating the points intersected by at least one line from each set. This paper describes an algorithm which locates all those vertices using O(kn2) time and O(kn) space. The method relies heavily on the topological plane sweep of Edelsbrunner and Guibas (1989).