首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Alternating Paths along Axis-Parallel Segments
Authors:Csaba D Tóth
Institution:(1) Department of Mathematics, MIT, Cambridge, MA 02139, USA
Abstract: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 MediaObjects/s00373-006-0669-9flb1.gif. 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.
Keywords:Alternating path  Geometric graph  Visibility
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号