Abstract
Let D be a connected region inside a simple polygon, P. We define the angle hull, \(\mathcal{A}\mathcal{H}\)(D), of D to be the set of all points in P that can see two points of D at a right angle. We show that the perimeter of \(\mathcal{A}\mathcal{H}\)(D) cannot exceed the perimeter of the relative convex hull of D by more than a factor of 2. A special case occurs when P equals the full plane. Here we prove a bound of π/2. Both bounds are tight, and corresponding results are obtained for any other angle.
This work was supported by the Deutsche Forschungsgemeinschaft, grant Kl 655/8-2.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
S. Carlsson and H. Jonsson. Computing a shortest watchman path in a simple polygon in polynomial-time. In Proc. 4th Workshop Algorithms Data Struct., volume 955 of Lecture Notes Comput. Sci., pages 122–134. Springer-Verlag, 1995.
S. Carlsson, H. Jonsson, and B. J. Nilsson. Finding the shortest watchman route in a simple polygon. In Proc. 4th Annu. Internat. Sympos. Algorithms Comput., volume 762 of Lecture Notes Comput. Sci., pages 58–67. Springer-Verlag, 1993.
W.-P. Chin and S. Ntafos. Watchman routes in simple polygons. Discrete Comput. Geom., 6(1):9–31, 1991.
X. Deng, T. Kameda, and C. Papadimitriou. How to learn an unknown environment. In Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci., pages 298–303, 1991.
X. Deng, T. Kameda, and C. H. Papadimitriou. How to learn an unknown environment I: the rectilinear case. Technical Report CS-93-04, Department of Computer Science, York University, Canada, 1993.
F. Hoffmann, C. Icking, R. Klein, and K. Kriegel. A competitive strategy for learning a polygon. In Proc. 8th ACM-SIAM Sympos. Discrete Algorithms, pages 166–174, 1997.
F. Hoffmann, C. Icking, R. Klein, and K. Kriegel. The polygon exploration problem: A new strategy and a new analysis technique. In Proc. 3rd International Workshop on Algorithmic Foundations of Robotics, 1998.
C. Icking and R. Klein. Searching for the kernel of a polygon: A competitive strategy. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 258–266, 1995.
C. Icking, R. Klein, and L. Ma. How to look around a corner. In Proc. 5th Canad. Conf. Comput. Geom., pages 443–448, 1993.
R. Seidel. Personal communication, 1997.
X. Tan and T. Hirata. Constructing shortest watchman routes by divide-and-conquer. In Proc. 4th Annu. Internat. Sympos. Algorithms Comput., volume 762 of Lecture Notes Comput. Sci., pages 68–77. Springer-Verlag, 1993.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hoffmann, F., Icking, C., Klein, R., Kriegel, K. (1998). Moving an angle around a region. In: Arnborg, S., Ivansson, L. (eds) Algorithm Theory — SWAT'98. SWAT 1998. Lecture Notes in Computer Science, vol 1432. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054356
Download citation
DOI: https://doi.org/10.1007/BFb0054356
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64682-2
Online ISBN: 978-3-540-69106-8
eBook Packages: Springer Book Archive