AbstractA k-dense corridor through a finite set, S, of n points in the plane is the open region of the plane that is bounded by two parallel lines that intersect the convex hull of S and such that the region contains k points of S. The problem of finding a widest k-dense corridor arises in robot motion-planning. In this paper, efficient solutions are presented for several versions of this problem. Results include: two algorithms for finding widest k-dense corridors for any k, an algorithm to dynamically maintain a widest empty corridor under online insertions and deletions in S, an algorithm to find a widest (n-1)-dense closed corridor, and a widest empty corridor algorithm for polygonal obstacles. The techniques used are based on geometric duality and on efficient searching in the convex layers of a point-set.
Categories and Subject Descriptors: E.1 [Data Structures]; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; I.2.9 [Artificial Intelligence]: Robotics
Additional Key Words and Phrases: arrangement, computational geometry, convex layers, data structures, geometric duality
Selected papers that cite this one
- Chan-Su Shin, Sung Yong Shin, and Kyung-Yong Chwa. The widest k-dense corridor problems. Information Processing Letters, 68(1):25-31, 15 October 1998.
Selected references
- Herbert Edelsbrunner and Leonidas J. Guibas. Topologically sweeping an arrangement. Journal of Computer and System Sciences, 38(1):165-194, February 1989.
- Herbert Edelsbrunner, Leonidas J. Guibas, and Jorge Stolfi. Optimal point location in a monotone subdivision. SIAM Journal on Computing, 15(2):317-340, May 1986.
- H. Edelsbrunner and E. Welzl. Constructing belts in two-dimensional arrangements with applications. SIAM Journal on Computing, 15(1):271-284, February 1986.