Characterizations of Star-Shaped, L-Convex, and Convex Polygons

Authors: Thomas Shermer, Godfried T. Toussaint

Abstract:

A chord of a simple polygon P is a line segment [xy] that intersects the boundary of P only at both endpoints x and y. A chord of P is called an interior chord provided the interior of [xy] lies in the interior of P. P is weakly visible from [xy] if for every point v in P there exists a point w in [xy] such that [vw] lies in P. In this paper star-shaped, L-convex, and convex polygons are characterized in terms of weak visibility properties from internal chords and starshaped subsets of P. A new Krasnoselskii-type characterization of isothetic star-shaped polygons is also presented.

Keywords: Convex polygons, L-convex polygons, star-shaped polygons, chords, weak visibility, discrete and computational geometry

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1334277

References:

[1] D. Avis. and G. T. Toussaint, "An optimal algorithm for determining the visibility of a polygon from an edge," IEEE Transactions on Computers, vol. C-30, No. 12, pp. 910-914, December 1981.
[2] D. Avis, G. T. Toussaint, and B. K. Bhattacharya, "On the multimodality of distances in convex polygons," Computers & Mathematics With Applications, vol. 8, No. 2, pp. 153-156, 1982.
[3] B. K. Bhattacharya and G. T. Toussaint, "A counterexample to a diameter algorithm for convex polygons," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI- No. 3, pp. 306-309, May 1982.
[4] M. Breen, "Krasnoselskii-type theorems," in Discrete Geometry and Convexity, Eds., J. E. Goodman et al., New York Academy of Sciences, 1985, pp.142-146.
[5] C. K. Bruckner and J. B. Bruckner, "On Ln-sets, the Hausdorff metric, and connectedness," Proceedings of the American Mathematical Society, vol. 13, pp. 765-767, 1962.
[6] G. Castiglioni, A. Frosini, A. Restivo, and S. Rinaldi, "Tomographical aspects of L-convex polyominoes," Pure Mathematics and Applications: Algebra and Theoretical Computer Science, (PU.M.A.), vol. 18, No. 3- 4, pp. 239-256, 2007.
[7] B. Chazelle, "Triangulating a simple polygon in linear time", Discrete & Computational Geometry, vol. 6, pp. 485-524, 1991.
[8] S. W. Dharmadhikari, and K. Jogdeo, "A characterization of convexity and central symmetry for planar polygonal sets," Israel Journal of Mathematics, vol. 15, pp. 356-366, 1973.
[9] H. ElGindy, D. Avis, and G. T. Toussaint, "Applications of a twodimensional hidden-line algorithm to other geometric problems," Computing, vol. 31, pp. 191-202, 1983.
[10] H. ElGindy, private communication, School of Computer Science and Engineering, University of New South Wales, Sydney, Australia, [email protected]
[11] I. Fary, "A characterization of convex bodies," American Mathematical Monthly, vol. 69, pp. 25-31, 1962.
[12] L. P. Gewali, "Recognizing s-star polygons," Pattern Recognition, vol. 28, no. 7, pp. 1019-1032, July 1995.
[13] B. Grunbaum, "Polygons," in The Geometry of Metric and Linear Spaces, A. Dold & B. Eckman, eds., Springer-Verlag, New York, 1965, pp.147-184.
[14] E. Helly, "Uber Mengen konvexer Korper mit gemeinshaftlichen Punkten," Jber. Deutsch. Math. Verein. vol. 32, 175-176, 1923.
[15] A. Horn and F. A. Valentine, "Some properties of L-sets in the plane," Duke Mathematics Journal, vol. 16, pp. 131-140, 1949.
[16] V. L. Klee, "A characterization of convex sets," American Mathematical Monthly, vol. 56, pp. 247-249, 1949.
[17] V. L. Klee, "What is a convex set?" The American Mathematical Monthly, vol. 78, no. 6, pp. 616-631, June-July 1971.
[18] M. A. Krasnoselskii, "Sur un critere qu-un domaine soit etoile, Math. Sb. vol. 61, No. 19, 1946.
[19] W. Lenhart, R. Pollack, J. Sack, R. Seidel, M. Sharir, S. Suri, G. T. Toussaint, S. Whitesides and C. Yap, "Computing the link center of a simple polygon," Discrete & Computational Geometry, vol. 3, 1988, pp. 281-293.
[20] J. M. Marr, and W. L. Stamey, "A three-point property," American Mathematical Monthly, vol. 69, pp. 22-25, 1962.
[21] J. Molnar, "Uber Sternpolygone," Publ. Math. Debrecen, vol. 5, pp. 241- 245, 1958.
[22] W. Nagel, "Orientation-dependent chord length distributions characterize convex polygons," Journal of Applied Probability, vol. 30, pp. 730-736, 1993.
[23] I. Pinelis, "A Characterization of the convexity of cyclic polygons in terms of the central angles," Journal of Geometry, vol. 87, pp. 106-119, 2007.
[24] E. E. Robkin, Characterizations of star-shaped sets, Ph.D. thesis, UCLA, 1965.
[25] T. Shermer, "On recognizing unions of two convex polygons and related problems," Pattern Recognition Letters, vol. 14, no. 9, pp. 737-745, 1993.
[26] C. R. Smith, "A characterization of star-shaped sets," The American Mathematical Monthly, vol. 75, no. 4, p. 386, April 1968.
[27] E. G. Strauss, and F. A. Valentine, "A characterization of finite dimensional convex sets," American Journal of Mathematics, vol. 74, pp. 683-686, 1952.
[28] S. Suri, "Minimum link paths in polygons and applications," Ph.D. Thesis, The Johns Hopkins University, Department of Computer Science, August 1987.
[29] H. Tietze, "Uber Konvexheit im kleinen und im grossen und uber gewisse den Punkten einer Menge zugeordnete Dimensionzahlen," Math. Z., vol. 28, pp. 697-707, 1928.
[30] G. T. Toussaint, "Complexity, convexity, and unimodality," International Journal of Computer and Information Sciences, vol. 13, No. 3, pp. 197-217, June 1984.
[31] G. T. Toussaint and H. ElGindy, "Traditional galleries are star-shaped if every two paintings are visible from some common point," Tech. Rept. SOCS-81.10, School of Computer Science, McGill University, March 1981.
[32] F. A. Valentine, "A three point convexity property," Pacific Journal of Mathematics, vol. 7, pp. 1227-1235, 1957.
[33] F. A. Valentine, "Local convexity and star-shaped sets," Israel Journal of Mathematics, vol. 3, pp. 39-42, March 1965.
[34] F. A. Valentine, "Local convexity and Ln-sets," Proceedings of the American Mathematical Society, vol. 16, pp. 1305-1310, 1965.
[35] F. A. Valentine, Convex Sets, McGraw-Hill, New York, 1964.
[36] F. A. Valentine, "Characterizations of convex sets by local support properties," Proc. Amer. Math. Soc.,vol. 11, pp. 112-116, 1960.
[37] I. M. Yaglom, and V. G. Boltyanskii, Convex Figures, Holt, Rinehart and Winston, New York, 1961.