## 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.
### Abstract

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`(`n`^{9}) 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`(`n`^{3})
viewing regions, according to
Theorem 4.19 of the book.
This is an improvement over the
trivial bound `O`(`n`^{4})
in my paper, and
it holds also for the complexity of the partition `Z`, of which the viewing
regions are a refinement:
`n`_{Z}=`O`(`n`^{3}).
This improves the overall bound of the paper from
`O`(`n`^{9})
to `O`(`n`^{7})
closed-form expressions.

Moral: *It can be worth while to read textbooks.*

Last update: July 12, 2017.