Alternating paths through disjoint line segments |
| |
| Authors: | Michael Hoffmann,Csaba D Tó th |
| |
| Affiliation: | a Institute for Theoretical Computer Science, ETH Zürich, CH-8092, Switzerland
b Department of Computer Science, University of California at Santa Barbara, CA 93106, USA |
| |
| Abstract: | We show that every segment endpoint visibility graph on n disjoint line segments in the plane admits an alternating path of length  , and this bound is optimal apart from a constant factor. |
| |
| Keywords: | Line segment Computational geometry Visibility graphs Hamiltonian circuit |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
