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

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.

Authors:

• Thomas Shermer
• Godfried T. Toussaint

Keywords:

• Convex polygons
• L-convex polygons
• star-shaped polygons
• chords
• weak visibility
• discrete and computational geometry

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.