FINDING DEGENERACIES AMONG SETS OF LINES

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