Günter Rote:

The degree of convexity

In: Abstracts of the 29th European Workshop on Computational Geometry (EuroCG'13), Braunschweig, March 2013, Editor: Sándor Fekete, pp. 69–72.


We measure the degree of convexity of a planar region by the probability that two randomly chosen points see each other inside the polygon. We show that, for a polygonal region with n edges, this measure can be evaluated in polynomial time as a sum of O(n9) closed-form expressions.

Note after publication (2017)

A region of a polygon in which the visible vertices are a fixed set of vertices is called a Sichtregion (viewing region) in the textbook of Rolf Klein, Algorithmische Geometrie (1996), Section 4.3.2. A polygon is partitioned into at most O(n3) viewing regions, according to Theorem 4.19 of the book. This is an improvement over the trivial bound O(n4) in my paper, and it holds also for the complexity of the partition Z, of which the viewing regions are a refinement: nZ=O(n3). This improves the overall bound of the paper from O(n9) to O(n7) closed-form expressions.

Moral: It can be worth while to read textbooks.

  pdf file (gzipped)
other papers about this subject
Last update: July 12, 2017.