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.