Finding the point within a convex n-gon that maximizes the least angle subtended there by an edge of the n-gon

Question

For any point P in the interior of a convex polygon, the sum of the angles subtended by the edges of the polygon is obviously 2π.

• Given a convex polygon, how does one algorithmically find the point (I don't know if it is unique) in its interior so that the least among angles subtended at this point by the edges of the polygon is maximized?

Remark 1: The question above has the property: minimizing the maximum (or maximizing the minimum) among a set of values does not automatically make all values equal unlike say, areas of n pieces into which a polygon is cut. An earlier question from the same ballpark is Cutting convex regions into equal diameter and equal least width pieces - 2

Remark 2: If the convex polygon is any triangle, the point minimizing the max subtended angle is unique - the Steiner point of the triangle.

Note 1: This question is based on this old note: https://nandacumar.blogspot.com/2007/04/triangulation-problem.html

Note 2: A couple of variants to the above question that were recorded in this very post have now been moved to a new post: Finding the point within a convex n-gon that minimizes the largest angle subtended there by an edge of the n-gon

Answer 1

This is about the issue of uniqueness, with a slight reformulation of the problem in view of an algorithmic approach.

Given a (closed) half-plane, a segment $e$ of its boundary, and $0<\theta<\pi$, denote $S(e,\theta)$ the set of all points $P$ of the half-plane such that the angle subtended at $P$ by the segment $e$ is not less than $\theta$. It is a disk segment cut off by the chord $e$ (and the angle subtended at $P$ is strictly larger that $\theta$ in its interior). A convex polygon with edges $e_1,\dots, e_n$ is the intersection of $n$ half-planes, each bounded by a line from an edge $e_i$, so a point $P$ sees all edges under an angle greater or equal than $\theta$ iff it is in the intersection $\bigcap_{1\le i\le n} S(e_i,\theta)$. This intersection, if not empty and not a singleton, is a strictly convex set with non-empty interior. The angles subtended at every point $P$ in its interior by the edges are all strictly larger than $\theta$, so that $\theta$ is not the maximum minimum angle. This shows that the point $P_*$ that maximises the least angle is unique.

edit. Some hints to determining the point $P_*$. Recall that the intersection of $n$ Euclidean disks is not empty iff every $3$-intersection (i.e. an intersection of three of them) is not empty. It follows that the intersection of $n$ Euclidean disks is a singleton iff all $3$-intersections are not empty, and at least one is a singleton. This means that the maximising point $P_*$ for all edges already solves the problem for some subset of $3$ of them. So a first rough procedure should be: solve the problem of the maxmin angle for all the triples of edges, and take the minimum. A smarter algorithm should avoid solving all ${n \choose 3}$ problems, of course.

Answer 2

This is about existence for both the max-min angle and the min-max angle problem. Existence of the optimiser is not immediately obvious for both, since the objective functions are combinations of angle functions $$X\mapsto \text{ang}(AXB):=\arccos \frac{(A-X)\cdot(B-X)}{\|A-X\|\|B-X\|}\in[0,\pi]$$ (for given points $A,B$ in the Euclidean plane), which are not defined for $X=A$ or $X=B$, nor have a continuous extension at these points, for in fact they have full oscillation there, equal to $\pi$.

Given a closed $n$-gon $C$ with vertices $V_0,V_1,\dots,V_n=V_0$ listed in cyclic order, a natural definition, for each $i$, is
$$\text{ang}(V_{i-1}V_iV_i)=\text{ang}(V_iV_iV_{i+1}):=\pi-\frac12\text{ang}(V_{i-1}V_iV_{i+1}).$$ (Pictorially, when $X\in C$ coincides with a vertex $V_i$, we may regard the segment $ XV_i$ as an outward directed infinitesimal segment of the bisectrix of the angle at $V_i$).

This way $\sum_{j=0}^{n-1} \text{ang}(V_jXV_{j+1})=2\pi$ for all $X\in C$, so the function $$C\ni X\mapsto \text{ang}(V_{i-1}XV_i)+\text{ang}(V_iXV_{i+1})=2\pi-\sum_{{j=0}\atop{j\neq i-1,j\neq i}}^{n-1} \text{ang}(V_jXV_{j+1}) $$ is continuous at $X=V_i$, and the function $$C\ni X\mapsto \big|\text{ang}(V_{i-1}XV_i)-\text{ang}(V_iXV_{i+1})\big|$$ is lower semi-continuous at $X=V_i$, for $$\liminf_{{X\to V_i}\atop {X\in C}} \big|\text{ang}(V_{i-1}XV_i)-\text{ang}(V_iXV_{i+1})\big|\ge\big|\text{ang}(V_{i-1}V_iV_i)-\text{ang}(V_iV_iV_{i+1})\big|=0.$$

Therefore the function

$$C\ni X\mapsto \max\big\{\text{ang}(V_{i-1}XV_i),\text{ang}(V_iXV_{i+1})\big\}=$$$$=\frac12\Big(\text{ang}(V_{i-1}XV_i)+\text{ang}(V_iXV_{i+1})+\big|\text{ang}(V_{i-1}XV_i)-\text{ang}(V_iXV_{i+1})\big|\Big)$$ is also lower semi-continuous at $X=V_i$ and the function $$C\ni X\mapsto \min\big\{\text{ang}(V_{i-1}XV_i),\text{ang}(V_iXV_{i+1})\big\}=$$$$=\frac12\Big(\text{ang}(V_{i-1}XV_i)+\text{ang}(V_iXV_{i+1})-\big|\text{ang}(V_{i-1}XV_i)-\text{ang}(V_iXV_{i+1})\big|\Big)$$ is upper semi-continuous at $X=V_i$. By consequence, the function $\alpha_*:C\to[0,2\pi]$ defined by

$$\alpha_*(X):=\min_{0\le j\le n-1}\text{ang}(V_jXV_{j+1})=$$$$ =\min\big\{\text{ang}(V_{i-1}XV_i),\text{ang}(V_iXV_{i+1})\big\}\wedge\min_{{0\le j\le n-1}\atop{j\neq i-1,j\neq i}} \text{ang}(V_jXV_{j+1})$$ is upper semi-continuous on $C$, and the function $\alpha^*:C\to[0,2\pi]$ defined by $$\alpha^*(X):=\max_{0\le j\le n-1}\text{ang}(V_jXV_{j+1})=$$$$ =\max\big\{\text{ang}(V_{i-1}XV_i),\text{ang}(V_iXV_{i+1})\big\}\vee\max_{{0\le j\le n-1}\atop{j\neq i-1,j\neq i}} \text{ang}(V_jXV_{j+1})$$ is lower semicontinuous on $C$. Hence, the USC function $\alpha_*$ attains its maximum on $C$ $$\theta_*:=\max_{X\in C}\min_{0\le j\le n-1}\text{ang}(V_jXV_{j-1}),$$ and every maximiser is interior to $C$ iff $$\max_{0\le i\le n-1}\min_{0\le j\le n-1}\text{ang}(V_jV_iV_{j+1})<\theta_*;$$ the LSC function $\alpha^*$ attains its minimum on $C$ $$\theta^*:=\min_{X\in C}\max_{0\le j\le n-1}\text{ang}(V_jXV_{j+1}).$$ and every minimiser is interior to $C$ iff $$\min_{0\le i\le n-1}\max_{0\le j\le n-1}\text{ang}(V_jV_iV_{j+1})>\theta^*.$$ (Rmk: The next step should be writing these conditions in a simpler equivalent form).

Incidentally, note that from the above identity $\sum_{j=0}^{n-1} \text{ang}(V_jXV_{j+1})=2\pi$ one has $\theta_*\le \frac{2\pi}n\le \theta^*$.