5
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ (i) According to these guidelines, users should "avoid trying to answer questions which [...] request answers to multiple questions". I see three questions here. (ii) You are saying "the point". I don't think such points are unique in general. $\endgroup$ Mar 26 at 12:43
  • $\begingroup$ Thank you. Made an edit - now there is only one main question and a couple of variants to the same theme (they are but variants on the same theme) are mentioned. And corrected the indication that the desired point is unique. $\endgroup$ Mar 26 at 16:39
  • $\begingroup$ When you say “not necessarily unique” you mean that you know there can be more than one or you mean that you don’t know if there can be more than one? (In fact I think this point should be unique) $\endgroup$ Mar 27 at 21:39
  • $\begingroup$ Thanks. I don't know - for triangles, the points are unique, as noted in the question. So, let me edit again leaving the question of uniqueness open. $\endgroup$ Mar 27 at 23:02
  • $\begingroup$ You can do a binary search. Then you have the polygon with a bunch of circles cut out from it, and you need to decide if it's not empty $\endgroup$ Mar 28 at 3:33

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Thanks! The argument for uniqueness feels very intuitive. and guess this is a nice application of Helly's theorem too. and regarding the algorithm proposed, one would guess/hope that improvement from O(n^3) would be possible via some randomized incremental approach. $\endgroup$ Mar 28 at 14:28
  • 1
    $\begingroup$ Marking this as an answered question. Reg the 'variants' mentioned above, would it now be more meaningful to shift them onto a separate question ? Hope to have an opinion on this. $\endgroup$ Mar 28 at 14:30
  • $\begingroup$ Yes, I think it should be OK moving the questions about variants of the problem to a nother post. $\endgroup$ Mar 28 at 14:56
  • $\begingroup$ (Thinking a bit more, it made sense to keep the two questions together, since they are really connected. The guidelines only suggests not to ask too different questions, or questions that require answering to different independent questions. My excuses!) $\endgroup$ Apr 1 at 9:59
  • 1
    $\begingroup$ But now rolling back the change made would be awkward - if the variants (there is more than one) moved to the new question are brought back, marking this question as 'answered' wouldn't be accurate. So, i would think the best course forward would be for the new question with variants also to receive an answer as satisfying as the one the present one has got (look forward to it) and get marked as answered. Thanks again. $\endgroup$ Apr 2 at 17:37
1
$\begingroup$

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^*$.

$\endgroup$
2
  • $\begingroup$ It could be that for $n$ large enough those conditions for the optimiser (either for $\alpha^*$ or $\alpha_*$) being interior are always verified: it is not clear to me. Note that for $n\ge4$ the minimum that defines $\alpha_*(V_i)$ can be done over $0\le j\le n-1$ and $j\neq i$, $j\neq i-1$ (because for $j=i$ and $j=i-1$ the corresponding angles are obtuse). $\endgroup$ Apr 11 at 8:15
  • $\begingroup$ I am yet to appreciate the full subtlety of the issues you point out. a general observation: unlike many other quantities (like say, distance), the subtended angle makes sense only if the boundary of a convex region is polygonal and not smooth. so in some sense, this particular type of optimization problems might not admit a 'neat' definition. $\endgroup$ Apr 15 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.