Bounded Degree Polyhedronization of Point Sets in R3
"The problem of finding a polyhedron in R3 with no four points coplanar, having the set of points as vertices, being simple in structure, with each vertex connected to O(1) edges, and featuring both a tetrahedralization and chain dual. This task has historical importance with Euler's formula setting a lower bound for the degree and subsequent advancements in polyhedronization algorithms."
Uploaded on Sep 22, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Bounded-Degree Polyhedronization of Point Sets Andrew Winslow with Gill Barequet, Nadia Benbernou, David Charlton, Erik Demaine, Martin Demaine, Mashhood Ishaque, Anna Lubiw, Andre Schulz, Diane Souvaine, and Godfried Toussaint
The Problem Let S be a set of points in R3with no four points coplanar.
The Problem Let S be a set of points in R3with no four points coplanar. Find a polyhedron P such that P:
The Problem Let S be a set of points in R3with no four points coplanar. Find a polyhedron P such that P: Has exactly S as vertices.
The Problem Let S be a set of points in R3with no four points coplanar. Find a polyhedron P such that P: Has exactly S as vertices. Is simple (sphere-like).
The Problem Let S be a set of points in R3with no four points coplanar. Find a polyhedron P such that P: Has exactly S as vertices. Is simple (sphere-like). Has every vertex incident to O(1) edges (degree = O(1)).
The Problem Let S be a set of points in R3with no four points coplanar. Find a polyhedron P such that P: Has exactly S as vertices. Is simple (sphere-like). Has every vertex incident to O(1) edges (degree = O(1)). Has a tetrahedralization and a chain dual (serpentine).
The Problem Let S be a set of points in R3 with no four points coplanar. Find a polyhedron P such that P: Has exactly S as vertices. Is simple (sphere-like). Has every vertex incident to O(1) edges (degree = O(1)). Has a tetrahedralization and a chain dual (serpentine).
History In 1700s, Euler s formula gave a lower bound of degree 6 for n > 12. In 1994, Gru nbaum showed that a polyhedronization is always possible. In 2008, Agarwal, Hurtado, Toussaint, and Trias gave several algorithms for serpentine polyhedronizations with non-constant degree.
In This Work We give an algorithm for computing a degree-7 serpentine polyhedronization of any point set. We show that the algorithm runs in expected time .
A High-Level Algorithm Start with the convex hull of the points. Shave off faces of the hull (triplets). Connect each triplet to the previous one with a six-vertex polyhedron (tunnel).
A High-Level Algorithm Start with the convex hull of the points. Shave off faces of the hull (triplets). Connect each triplet to the previous one with a six-vertex polyhedron (tunnel).
A High-Level Algorithm Start with the convex hull of the points. Shave off faces of the hull (triplets). Connect each triplet to the previous one with a six-vertex polyhedron (tunnel).
A High-Level Algorithm Start with the convex hull of the points. Shave off faces of the hull (triplets). Connect each triplet to the previous one with a six-vertex polyhedron (tunnel).
A High-Level Algorithm Start with the convex hull of the points. Shave off faces of the hull (triplets). Connect each triplet to the previous one with a six-vertex polyhedron (tunnel).
A High-Level Algorithm Start with the convex hull of the points. Shave off faces of the hull (triplets). Connect each triplet to the previous one with a six-vertex polyhedron (tunnel).
Tunnels The degree of a vertex is the number of edges in both of its tunnels. Each triplet contributes 1 + 2 + 3 edges. Each tunnel is composed of three tetrahedra.
Degree-8 Bound In the worst case, a vertex p of Timay have three edges in both tunnels. So degree(p) = 8 (= 2 + 3 + 3). This can be avoided with more careful selection of Ti+1.
Selecting Ti+1Carefully Label vertices of Ti according to number of edges in previous tunnel (wi got 3). Perform double rotation to find Ti+1 requiring just one edge to wi. This gives a worst-case degree of 7.
Reaching Degree Optimality Recall the lower bound of 6 for n > 12. Open Problem #1: Is there a point set that admits only degree-7 polyhedronizations? Open Problem #2: Is there an algorithm that produces a degree-6 polyhedronization? Improving our algorithm to degree-6 would produce a long sequence of tunnels where every vertex has degree 6.
Serpentine Recall that each tunnel consists of three tetrahedra. Their dual is a short chain. Adjacent tunnels connect at their ends. So the polyhedronization is serpentine.
Running Time The algorithm runs in expected time. Uses dynamic convex hull (Chan 2010) to find the next Ti and update the convex hull in expected time .
Conclusion We gave an expected-time algorithm that computes a degree-7 serpentine polyhedronization of any point set. The algorithm uses iterative convex hulls to connect triplets of points with tunnels.
References B. Gru nbaum, Hamiltonian polygons and polyhedra. Geombinatorics, 3 (1994), 83 89. P. Agarwal, F. Hurtado, G.T. Toussaint, and J. Trias, On polyhedra induced by point sets in space, Discrete Applied Mathematics, 156 (2008), 42 54. T. Chan, A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries, Journal of the ACM, 57 (2010), 1-16.
