Walking in an arrangement topologically. (English) Zbl 0820.68121
Summary: We present topological walk, an on-line algorithm for computing a walk in an arrangement. Here, a walk is a visit to the cells of an arrangement in an order such that consecutive cells are adjacent to each other. The algorithm can walk in a part of an arrangement efficiently; more precisely, given an arrangement of \(n\) lines in a convex region containing \(K\) cells, a walk is performed in \(O(K+ n\log n)\) time and \(O(n)\) working space. Several optimal-cell-finding problems can be solved efficiently applying the topological walk. Further, a construction of a spanning tree with maximum node degree three of the dual graph of an arrangement is given.
MSC:
68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |