Alternating Paths along Axis-Parallel Segments

It is shown that for a set S of n pairwise disjoint axis-parallel line segments in the plane there is a simple alternating path of length . This bound is best possible in the worst case. In the special case that the n pairwise disjoint axis-parallel line segments are protruded (that is, if the intersection point of the lines through every two nonparallel segments is not visible from both segments), there is a simple alternating path of length n. Work on this paper was partially supported by National Science Foundation grants CCR-0049093 and IIS-0121562. A preliminary version of this paper has appeared in the Proceedings of the 8th International Workshop on Algorithms and Data Structures (Ottawa, ON, 2003), vol. 2748 of Lecture Notes on Computer Science, Springer, Berlin, 2003, pp. 389–400.