# Menagerie of polygons

UPDATE

Now community wiki. My new version of the question is: let's make a big list of classes of polygons. We may be able to produce the most comprehensive list on the web, or in the literature. If there is community interest, after Jan 1st I will organize the information from all the answers into a post on the community blog.

ORIGINAL QUESTION BELOW

Could you recommend a source, either in print or online, for a menagerie of polygons? An extensive/exhaustive list of classes of polygon?

The Wikikpedia article on polygons provides a partial classification, but I would like something more complete. Also, I am not concerned about how to name a 90-sided figure. Rather, I am trying to find a list of classes that contain infinitely many figures each (examples: star polygon, isothetic polygon).

For example: actual words for "looks like a spider," "would look like a football if it were smoothed out," and so on.

I've already checked The Geometry Junkyard and several pages of a Google search, but perhaps I didn't know what to look for.

Thanks very much.

• For those of us who like me are not native English speakers: here's a definition of a menagerie – Anthony Labarre Dec 7 '11 at 20:40
• There's a small listing in Subhash Suri's survey "Polygons" in the Handbook of Discrete and Computational Geometry. But I hesitate to make this an answer rather than a comment, because it's less complete than the Wikipedia article you already list. It lists only simple, convex, monotone, star-shaped, and orthogonal polygons. See also staff.science.uu.nl/~kreve101/papers/personpoly.pdf for some more obscure types of polygon. – David Eppstein Dec 7 '11 at 22:25
• The paper cited by @DavidEppstein is worth it just for its observation that distinguishing "the male person polygons from the female person polygons" is an open problem that "may be easier to solve in 3-dimensional space than in the plane." Priceless. – mjqxxxx Dec 8 '11 at 4:23
• @DavidEppstein:Thanks for the pointers, but, more importantly, CONGRATULATIONS on becoming an ACM Fellow. :-) – Aaron Sterling Dec 8 '11 at 19:15
• Aaron, what do you think about @DavidEppstein's suggestion to make this CW ? – Suresh Venkat Dec 9 '11 at 4:57

Godfried reports that his hierarchy paper (cited by Aaron) never got written, but some of its ideas appeared in these two papers.

• Hossam A. ElGindy, Godfried T. Toussaint. "On geodesic properties of polygons
relevant to linear time triangulation," The Visual Computer.

• Godfried T. Toussaint, "Movable separability of sets," in Computational
Geometry
, Ed., G. T. Toussaint, North-Holland, 1985.

Here is a figure from the first: Note that the shapes mentioned in Yoshio Okamoto's post appear in this hierarchy. And if you are wondering what a (Barbados-induced?) "palm" polygon looks like... I think(?) I [Joe O'Rourke] was the first to introduce monotone mountains, but perhaps I copied that class from someone else. It is a subclass of monotone polygons, with one of the two chains that constitutes a monotone polygon a single segment. I used it in the paper, "Vertex pi-lights for monotone mountains," 9th Canad. Conf. Comput. Geom., Aug. 1997, pp. 1-5. Joe Mitchell subsequently used this class of polygons in his abstract, "Triangulating Monotone Mountains," AMS 345/CSE 355 (PDF link).

Maybe it would make sense to make this question community wiki and solicit answers that describe additional individual classes of polygons, since a proper survey seems to be lacking (although I did run across some references to a manuscript by Toussaint)?

If so, here's another one: pseudotriangles, polygons that have only three convex vertices and all the rest concave.

Also, O'Rourke's book "Art Gallery Theorems and Algorithms" has a section on "spiral polygons", polygons whose concave vertices form a single contiguous subsequence of the boundary.

• Hazel Everett wrote her Ph.D. thesis (under Derek Corneil) on spiral polygons: "Recognizing Visibility Graphs of Spiral Polygons," J. Algorithms, 1990: 1-26. – Joseph O'Rourke Dec 9 '11 at 12:38

"Two-Convex Polygons," O. Aichholzer, F. Aurenhammer, F. Hurtado, P.A. Ramos, J. Urrutia, 2009. A polygon is $k$-convex if and only if its stabbing number is at most $2k$.

Another class of polygons is called anthropomorphic: these polygons have exactly two ears and one mouth.

Godfried T.Toussaint, "Anthropomorphic Polygons." American Mathematical Monthly 122, 31-35, 1991.

Grunbaum wrote a long paper describing many classes of crossing polygons here: Branko Grunbaum, "Polygons," In The Geometry of Metric and Linear Spaces, L. M. Kelly, ed. Lecture Notes in Mathematics Number 490, pp. 147 - 184. Springer-Verlag, Berlin-Heidelberg-New York 1975.

This is not a serious answer, just an opportunity to mention that Godfried Toussaint introduced sail polygons in his 1985 paper "A simple linear algorithm for intersecting convex polygons": I don't think this particular class found many subsequent uses. :-)

• There is an unpublished manuscript of Toussaint that is supposed to have a collection of polygons, "A hierarchy of simple polygons." I am unable to find it online. Do you know if it ever appeared in any form? – Aaron Sterling Dec 8 '11 at 20:16
• And then what do we call the union of a human polygon and a sail polygon ? :) – Suresh Venkat Dec 8 '11 at 23:13
• @Aaron: I have a query in to Godfried, and will let you know eventually. – Joseph O'Rourke Dec 9 '11 at 14:25

The following paper by Hernando, Houle, and Hurtado introduces a few classes of simple polygons in terms of visibility.

Now I describe the definitions of their polygons.

Edge-visible polygons

Let $e$ be an edge of a simple polygon $P$. Then, $P$ is edge-visible from $e$ if for every point $p$ of $P$ there exists a point $q$ on the relative interior of $e$ such that the relative interior of the line segment connecting $p$ and $q$ completely lies outside of $P$.

Externally visible polygons

A simple polygon is externally visible if for every point $p$ on the boundary of $P$ there exists a ray (half line) $r$ starting at $p$ that intersects $P$ only at $p$.

Monotone polygons, star-shaped polygons and pseudo-triangles are externally visible.