Timeline for Surfaces generated by minimum-weight triangulations
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 12, 2021 at 20:01 | comment | added | Joseph O'Rourke | @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." | |
| Feb 12, 2021 at 16:50 | comment | added | Manfred Weis | 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). | |
| Feb 10, 2021 at 18:06 | history | edited | Joseph O'Rourke | CC BY-SA 4.0 |
deleted 134 characters in body
|
| Feb 10, 2021 at 18:04 | comment | added | Joseph O'Rourke | @ManfredWeis: Oh, sorry, I missed "closed." So in fact directly relevant. Will edit. | |
| Feb 10, 2021 at 18:02 | comment | added | Manfred Weis | I had asked for closed 3D curves, so the articles related to 3D polygons perfectly fit my question. | |
| Feb 10, 2021 at 17:59 | vote | accept | Manfred Weis | ||
| Feb 10, 2021 at 17:45 | history | edited | Joseph O'Rourke | CC BY-SA 4.0 |
added 66 characters in body
|
| Feb 10, 2021 at 17:39 | history | answered | Joseph O'Rourke | CC BY-SA 4.0 |