# Wheel-graph with minimal spoke-weight sum centered at a planar-euclidean point

Questions:

• Given a set $$\mathcal{P}$$ of points in the Euclidean plane, what is the complexity of finding for a given point $$p_i$$ inside the convex hull $$\mathrm{CH}\left(\mathcal{P}\right)$$ the set $$\lbrace q_{ij}\rbrace\subseteq\mathcal{P}\setminus p_i\$$ that minimizes $$\sum\limits_{j}\left\|q_{ij}-p_i\right\|$$ and for which every line through $$p_i$$ has points from $$\lbrace q_{ij} \rbrace$$ to both sides?

• is the subgraph induced by the edge-set set $$\lbrace\lbrace p_i, q_{ij}\rbrace\rbrace$$ connected?

remark:

$$\bigcup\limits_i\bigcup\limits_j (p_i,q_{ij})$$ partitions the convex-combination of $$\mathcal{P}$$ into convex polygonal regions whose minimum-weight triangulation together with the edges of the convex hull $$\mathrm{CH}(\mathcal{P})$$ and $$\bigcup\limits_i\bigcup\limits_j (p_i,q_{ij})$$ may yield a good approximation of $$\mathcal{P}$$'s minimum-weight triangulation.

• I think you mean $\cal{P} \setminus p_i$? And I don't see the role of the index $j$. Could you explain? – Joseph O'Rourke Dec 12 '20 at 18:22
• the index was missing; icorrected that. I decided to use the double index because just using$\lbrace q_j\rbrace$ for the spoke-vertices would not allow to identify the center-point from a set in the collection of all those sets for agiven pointset; if there are better ways o express what I describe, I will be glad to reformulate. – Manfred Weis Dec 12 '20 at 18:36
• The sum should be for $j$. – domotorp Dec 12 '20 at 21:45
• Am I right with my observation that the sets you‘re looking for have size 3? – Patrick Schnider Dec 13 '20 at 20:25
• @PatrickSchnider yes, you are right, So the question about the complexity, resp. most efficient algorithm remains. I have some ideas that I will post. – Manfred Weis Dec 14 '20 at 8:20

## 1 Answer

That should actually be a seen as comment:

It appears as an $$O(n^2)$$ is possible: suppose $$q_{ij}, q_{ik}$$ are given and $$\varphi(q_{ij})=0^\circ$$ and $$0^\circ\lt\varphi(q_{ik})\le 180^\circ$$ then the 3rd point must satisfy $$180^\circ\lt\varphi(q_{ih})\le 180^\circ+\varphi(q_{ik})$$. Here $$\varphi(q_{ik})$$ is the angle of that point in a polar coordinate system with $$p_i$$ as the origin and a suitably chosen reference direction.

So we are looking for the nearest point in an angular range; that however amounts to a range minimum query that can be answered in $$O(1)$$ time per query and $$O(n)$$ preprocessing.
A further improvement would be to determine the halfplane through $$p_i$$ that contains the fewest elements of $$\lbrace q_{ij}\rbrace$$ and iterate over the pairs in that set.