Hiding points in arrangements of segments. (English) Zbl 0874.68296
Summary: A hidden set is a set of points such that no two points in the set are visible to each other. In this paper we study hidden sets of points in arrangements of segments, and we provide bounds for its maximum size that are optimal up to a factor 2.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
hidden setReferences:
| [1] | Aggarwal, A., The art gallery problem: Its variations, applications and algorithmic aspects, (Ph.D. Thesis (1984), John Hopkins University) |
| [2] | Breen, M., The combinatorial structure of \((m, n)\)-convex sets, Israel J. Math., 15, 367-374 (1973) · Zbl 0271.52001 |
| [3] | Breen, M., A decomposition theorem for \(m\)-convex sets, Israel J. Math., 24, 211-216 (1976) · Zbl 0342.52005 |
| [4] | Breen, M.; Kay, D., General decomposition theorems for \(m\)-convex sets in the plane, Israel J. Math., 24, 217-233 (1976) · Zbl 0342.52006 |
| [5] | Chvátal, V., A combinatorial theorem in plane geometry, J. Combin. Theory Ser. B, 18, 39-41 (1975) · Zbl 0278.05028 |
| [6] | Czyzowicz, J.; Rivera, E.; Urrutia, J., Illuminating rectangles and triangles on the plane, University of Ottawa Computer Science TR-89-50 (1989) |
| [7] | Czyzowicz, J.; Rivera, I.; Urrutia, J., Galleries and light matchings: Fat cooperative guards, (Melter, R.; Rosenfeld, A.; Bhattacharya, P., Vision Geometry (1991), Amer. Mathematical Soc: Amer. Mathematical Soc Providence, RI), 21-28 · Zbl 0728.05023 |
| [8] | Czyzowicz, J.; Rivera, E.; Urrutia, J.; Zaks, J., Illuminating lines and circles on the plane, University of Ottawa Computer Science TR-89-49 (1989) |
| [9] | Czyzowicz, J.; Rivera, E.; Urrutia, J.; Zaks, J., Illuminating and guarding segments on the plane, (Informatique RR-90/09-13 (1990), Université du Québec a Hull) |
| [10] | Erdös, P.; Szekeres, G., A combinatorial problem in geometry, Compositio Math., 2, 463-470 (1935) · JFM 61.0651.04 |
| [11] | Fredman, M. L., On computing the length of the longest increasing subsequence, Discrete Math., 11, 29-35 (1975) · Zbl 0312.68027 |
| [12] | Guay, M.; Kay, D., On sets having finitely many points of local nonconvexity and property \(P_m\), Israel J. Math., 10, 196-209 (1971) · Zbl 0228.52002 |
| [13] | Hurtado, F., Problems Geométricos de Visibilidad, (Ph.D. Dissertation (January 1993), Universitat Politécnica de Catalunya), (in Spanish) |
| [14] | Kay, D.; Guay, M., Convexity and a certain property \(P_m\), Israel J. Math., 8, 39-52 (1970) · Zbl 0203.24701 |
| [15] | Knuth, D. E., (The Art of Computer Programming, Vol. 3 (1973), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0302.68010 |
| [16] | Lee, D.; Lin, A., Computational complexity of art gallery problems, IEEE Trans. Inform. Theory, 32, 276-282 (1986) · Zbl 0593.68035 |
| [17] | O’Rourke, J., Art Gallery Theorems and Algorithms (1987), Oxford University Press: Oxford University Press Oxford · Zbl 0653.52001 |
| [18] | Shermer, T., Hiding people in polygons, Computing, 42, 109-131 (1989) · Zbl 0675.68070 |
| [19] | Shermer, T., Recent results in art galleries, (Toussaint, G. T., Special issue of Proc. IEEE (September 1992)) · Zbl 0675.68070 |
| [20] | Valentine, F., A three point convexity property, Pacific J. Math., 7, 1227-1235 (1957) · Zbl 0080.15401 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
