TY - GEN
T1 - Walking on an arrangement topologically
AU - Asano, Tetsuo
AU - Guibas, Leonidas J.
AU - Tokuyama, Takeshi
N1 - Publisher Copyright:
© 1991 ACM.
PY - 1991/6/1
Y1 - 1991/6/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0042446808&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0042446808&partnerID=8YFLogxK
U2 - 10.1145/109648.109690
DO - 10.1145/109648.109690
M3 - Conference contribution
AN - SCOPUS:0042446808
SN - 0897914260
T3 - Proceedings of the Annual Symposium on Computational Geometry
SP - 297
EP - 306
BT - Proceedings of the Annual Symposium on Computational Geometry
PB - Association for Computing Machinery
T2 - 7th Annual Symposium on Computational Geometry, SCG 1991
Y2 - 10 June 1991 through 12 June 1991
ER -