• 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?


$\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.

  • $\begingroup$ I think you mean $\cal{P} \setminus p_i$? And I don't see the role of the index $j$. Could you explain? $\endgroup$ – Joseph O'Rourke Dec 12 '20 at 18:22
  • 1
    $\begingroup$ 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. $\endgroup$ – Manfred Weis Dec 12 '20 at 18:36
  • 1
    $\begingroup$ The sum should be for $j$. $\endgroup$ – domotorp Dec 12 '20 at 21:45
  • 1
    $\begingroup$ Am I right with my observation that the sets you‘re looking for have size 3? $\endgroup$ – Patrick Schnider Dec 13 '20 at 20:25
  • $\begingroup$ @PatrickSchnider yes, you are right, So the question about the complexity, resp. most efficient algorithm remains. I have some ideas that I will post. $\endgroup$ – Manfred Weis Dec 14 '20 at 8:20

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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