3
$\begingroup$

The minimum-weight triangulation of simple polygons can be efficiently calculated in $O(n^3)$ time by dynamic programming, while it is $\text{NP-hard}$ for pointsets in general.

Looking at the dynamic-programming algorithm, one sees that it also works for Hamilton cycles in symmetric graphs with arbitrarily weighted edges.

Question:

what are the differential-geometric properties of surfaces that result from calculating the minimum-weight triangulations of points that are distributed along a rectifiable closed 3D curve as the number of points increases and the maximal distance between neighboring points tends to $0$; will that be the minimum-area surface defined by the curve?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ This way you can get only ruled surfaces, and minimal surfaces are not ruled in general. So for sure one can not get an area-minimizing surface in the limit. $\endgroup$
    – Anton Petrunin
    Commented Feb 10, 2021 at 17:58

1 Answer 1

Reset to default
1
$\begingroup$

My guess is that a minimum edge-weight triangulation would not in general lead to a minimum-area surface. Instead a minimum-area triangulation might.

There is a considerable literature on triangulations of 3D polygons. You probably know that triangulating a 3D polygon is NP-hard (a 1995 result).

Here is one relatively recent paper that cites many others. The leftmost images in their figure minimize the area. In general, the resulting surface is quite sensitive to the function optimized, which suggests your min-area hypothesis/hope may not be realized.

Zou, Ming; Ju, Tao; and Carr, Nathan, "Delaunay-restricted Optimal Triangulation of 3D Polygons." Report Number: WUCSE-2012-45 (2012). PDF download.

ZTC

Improve this answer
$\endgroup$
4
  • $\begingroup$ I had asked for closed 3D curves, so the articles related to 3D polygons perfectly fit my question. $\endgroup$
    – Manfred Weis
    Commented Feb 10, 2021 at 18:02
  • $\begingroup$ @ManfredWeis: Oh, sorry, I missed "closed." So in fact directly relevant. Will edit. $\endgroup$
    – Joseph O'Rourke
    Commented Feb 10, 2021 at 18:04
  • $\begingroup$ I just noticed a little misinterpretation of what triangulating a 3D polygon means; citing from "On Triangulating 3-Dimensional Polygons" by Barequet, Dickersen and Eppstein: "A three-dimensional polygon is triangulable if it has a non-selfintersecting triangulation which defines a simply connected 2-manifold". That is however more restrictive than blindly applying the dynamic programming algorithm to the distance graph of a 3D polygon (what I had originally in the back of my mind). $\endgroup$
    – Manfred Weis
    Commented Feb 12, 2021 at 16:50
  • $\begingroup$ @ManfredWeis: Yes, the NP-hardness depends on non-self-intersection: "If we allow self-intersecting triangulations (in contrast with our definition), then computing the optimal triangulation can be done (in cubic time) by applying a simple dynamic-programming procedure." $\endgroup$
    – Joseph O'Rourke
    Commented Feb 12, 2021 at 20:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .