Degree of Convexity and Expected Distances in Polygons
share
We present an algorithm for computing the so-called Beer-index of a polygon P in O(n^2) time, where n is the number of corners. The polygon P may have holes. The Beer-index is the probability that two points chosen independently and uniformly at random in P can see each other. Given a finite set M of m points in a simple polygon P, we also show how the number of pairs in M that see each other can be computed in O(nlog n+m^4/3log^α mlog n) time, where α<1.78 is a constant. We likewise study the problem of computing the expected geodesic distance between two points chosen independently and uniformly at random in a simple polygon P. We show how the expected L_1-distance can be computed in optimal O(n) time by a conceptually very simple algorithm. We then describe an algorithm that outputs a closed-form expression for the expected L_2-distance in O(n^2) time.
READ FULL TEXT