Topological Walk Revisited

Tetsuo ASANO  Takeshi TOKUYAMA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E81-A   No.5   pp.751-756
Publication Date: 1998/05/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
algorithm,  arrangement of lines,  computational geometry,  degeneracy,  duality transform,  

Full Text: PDF(559.3KB)>>
Buy this Article




Summary: 
Topological Walk is an algorithm that can sweep an arrangement of n lines in O(n2) time and O(n) space. This paper revisits Topological Walk to give its new interpretation in contrast with Topological Sweep. We also survey applications of Topological Walk to make the distinction clearer.