This question is motivated by an almost successful attempt to define planar convex hulls of a finite set of isolated points only via subset sums of the distances between point-pairs; the advantage of such a definition would be its immediate applicability to weighted symmetric graphs, even if no straignt-line embedding into the euclidean plane is possible.

The original idea, that led nowhere, was to generalize the notion of convexity to $K4$ subgraphs and, if that had been possible, to remove from "non-convex" $K4$ the vertex, that is no corner of the largest triangle.

A minor success was the identification of a sufficient criterion for the convexity of planar embeddings of $K4$, namely that the two longest edges constitute to the maximum-weight matching.
Identifying those $K4$ in planar pointsets and removing their maximum-weight edges preserved the convex hull, but the remaining set of edges was still quite dense (experimentation with about 500 points randomly distributed in a square indicated an average degree of about 16).

Now, the big surprise and the subject of this question is based on a different observation: one of the edges constituting to the maximum-weight matching is always inside the convex of the planar embedding of $K4$'s vertices, namely the one, that is not a side of the largest triangle. Removing those "inner diagonals" also preserved the convex hull, but left only very very few extra edges.


  • are there non-trivial bounds for the edges, that are not on the convex hull and are not "inner diagonals" (as described above)?

  • are there other criteria (purely based on length-sums and adjacency relations) that would allow the removal of further edges that are not on the convex hull

  • is it possible to decide, whether (for sufficiently large sets of points) all edges that are not on the convex hull, can be identified and removed via criteria, that are only based on length-sums and adjacency-relations of planar embeddings of $K4$?


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.