Finding the Point with Maximum Distance from the Boundary of a Closed Polygon in 2D Euclidean Space

Question

Given a closed polygon defined in the 2D Euclidean plane. My objective is to determine the point within this polygon that is furthest away from its boundary. In other words, I want to find the point where the distance to the polygon's boundary is maximized.

More formally, given a polygon $P \in \mathbb{R}^2$, for any point $x\in P$ we define $D_P(x) = \min_{y\in \partial P}dist(x,y)$. We wish to find a point $x\in P$ which maximizes $D_P(x)$.

Here are my specific questions:

1. Is there an analytical or closed-form equation for finding the point with the maximum distance from the boundary of a closed polygon in 2D Euclidean space, expressed as a function of the polygon's vertices?

2. How can I algorithmically find such point?

3. More generally, can the above be solved for a connected convex set in a d--dimensional Euclidean space instead of a polygon, how would the approach change? Are there general methods for solving this problem in higher dimensions?

I'd appreciate any insights, algorithms, or references that can help me achieve this goal.

Answer 1

The medial axis is the set of points in the interior of the shape that has two closest points on the boundary.

The medial axis of a polygon

Intuitively, the largest "incircle" in a polygon must touch the boundary at at least three points. It follows that you can just consider the set of points that are the "junctions" on the medial axis: points where three line segments of the medial axis meet.

To compute the medial axis for a simple polygon, linear algorithms are known, although it may be worth using a simpler $O(n \log n)$ algorithm. See:

• Chin et al, Finding the Medial Axis of a Simple Polygon in Linear Time , Discrete & Computational Geometry, v. 21, pp 405–420 (1999)

The cells formed by the boundary and the medial axis is known as a generalised Voronoi diagram; it's generalised because some of the "points" are the boundary lines. There are plenty of software packages out there that compute generalised Voronoi diagrams.

• Meni: Thanks for the answer! About the statement "the largest "incircle" in a polygon must touch the boundary at at least three points". Take a rectangle with width 10 and height 4. There are pints within distance 2 from the upper and lower sides which are not within distance 2 from any other side. What am I missing here?
• Tassle: @Meni But there exists a point which is at distance 2ドル$ from 3ドル$ of the sides. If you want just one point maximizing the distance to the border, then this answer stands (as long as you consider also the endpoints of the medial axis, in addition to the junctions).
• Meni: @Tassle Oh ok, got it. Makes sense. Thank you for the clarification.
• Pseudonym: The word "intuitively" is clearly doing a lot of heavy lifting in my answer.