Topological peeling and applications

We present a new approach, called topological peeling, for traversing a portion A_R of the arrangement formed by n lines within a convex region R on the plane. Topological peeling visits the cells of A_R in a fashion of propagating a "wave" of a special shape (called a double-wriggle curve) starting at a single source point. This special traversal fashion enables us to solve several problems (e.g., computing shortest paths) on planar arrangements to which previously best known arrangement traversal techniques such as topological sweep and topological walk may not be directly applicable. Our topological peeling algorithm takes O(K + n log(n + r)) time and O(n + r) space, where K is the number of cells in A_R and r is the number of boundary vertices of R. Comparing with topological walk, topological peeling uses a simpler and more efficient way to sweep different types of lines, and relies heavily on exploring small local structures, rather than a much larger global structure. Experiments show that, on average, topological peeling outperforms topological walk by 10-25% in execution time.