Walking on an arrangement topologically

Abstract

We present topological walk, which is an on-line algorithm to give a walk of an arrangement. Here, a walk is a list of cells of the arrangement in which consecutive cells are adjacent to each other. The algorithm is input-sensitive; in precise, given an arrangement of n lines in a convex region which contains K cells, a walk is given in O(K+ n log n) time and O(n) working space. Further, we can efficiently solve several optimal cell finding problems applying topological walk.