Constant-Work-Space Algorithm for a Shortest Path in a Simple Polygon
スポンサーリンク
概要
- 論文の詳細を見る
We present two space-efficient algorithms. First, we show how to report a simple path between two arbitrary nodes in a given tree. Using a technique called "computing instead of storing", we can design a naive quadratic-time algorithm for the problem using only constant work space, i.e., O(logn) bits in total for the work space, where n is the number of nodes in the tree. Then, another technique "controlled recursion" improves the time bound to O＾(n 1 + ε ) for any positive constant ε. Second, we describe how to compute a shortest path between two points in a simple n-gon. Although the shortest path problem in general graphs is NL-complete, this constrained problem can be solved in quadratic time using only constant work space.WALCOM: Algorithms and Computation, 4th International Workshop, WALCOM 2010, Dhaka, Bangladesh, February 10-12, 2010. Proceedings
- Springerの論文
- 2010-02-03
Springer | 論文
- Comparisons of germination traits of alpine plants between fellfield and snowbed habitats
- Photoreceptor Images of Normal Eyes and of Eyes with Macular Dystrophy Obtained In Vivo with an Adaptive Optics Fundus Camera
- Effect of Electrical Stimulation on IGF-1 Transcription by L-Type Calcium Channels in Cultured Retinal Muller Cells
- In Vivo Measurements of Cone Photoreceptor Spacing in Myopic Eyes from Images Obtained by an Adaptive Optics Fundus Camera
- Optical Quality of the Eye Degraded by Time-Varying Wavefront Aberrations with Tear Film Dynamics