Degree of Convexity and Expected Distances in Polygons

2022/08/15 by Mikkel Abrahamsen, Abrahamsen, Mikkel, Viktor Fredslund-Hansen +1
Computer Science · Social Sciences · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Geographic Information Systems Studies #Metric Geometry (math.MG)

paper · pdf · doi:10.48550/arxiv.2208.07106

openalex publication_date 2022/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present an algorithm for computing the so-called Beer-index of a polygon P in O(n²) 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₁-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₂-distance in O(n²) time.

Related

• The moments of the distance between two random points in a regular polygon
• Random Distances Associated with Arbitrary Triangles: A Systematic Approach between Two Random Points
• Probability that n points are in convex position in a general convex polygon: Asymptotic results
• Large convex holes in random point sets
• The Geodesic Fréchet Distance Between Two Curves Bounding a Simple Polygon