Technical Reports

Reporting all intersections of line segments and their characteristics is one of the early and most fundamental problems in computational geometry. We concentrate on the problem of reporting all intersections in an embedding of a complete graph that may contain degeneracies such as vertical lines, or multiply intersecting lines. A graph presents some difficulties for a sweep line algorithm that most of the existing sweep based algorithms do not handle. We present a novel approach that sweeps a complete graph of vertices and intersection points in optimal time and space, that is simple and easy to code. The algorithm sweeps the graph using a topological line, borrowing the concept of horizon trees from the topological sweep method (Edelsbrunner & Guibas 89) and using ideas from Rafalin et al. 02 to deal with degeneracies. The novelty in our approach is the use of the moving wall that separates at any time the graph into two regions: the region of known structure, in front of the moving wall, and the region that may contain intersections generated by edges that have not yet been registered in the sweep process, behind the wall. The algorithm has applications in computing the simplicial depth median for a set of data points The paper includes the algorithm, its analysis and experimental results.