In
computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...
, the star unfolding of a
convex polyhedron
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...
is a
net
Net or net may refer to:
Mathematics and physics
* Net (mathematics), a filter-like topological generalization of a sequence
* Net, a linear system of divisors of dimension 2
* Net (polyhedron), an arrangement of polygons that can be folded up ...
obtained by cutting the polyhedron along
geodesic
In geometry, a geodesic () is a curve representing in some sense the shortest path ( arc) between two points in a surface, or more generally in a Riemannian manifold. The term also has meaning in any differentiable manifold with a connection. ...
s (shortest paths) through its faces. It has also been called the inward layout of the polyhedron, or the Alexandrov unfolding after
Aleksandr Danilovich Aleksandrov
Aleksandr Danilovich Aleksandrov (russian: Алекса́ндр Дани́лович Алекса́ндров, alternative transliterations: ''Alexandr'' or ''Alexander'' (first name), and ''Alexandrov'' (last name)) (4 August 1912 – 27 July 19 ...
, who first considered it.
Description
In more detail, the star unfolding is obtained from a polyhedron
by choosing a starting point
on the surface of
, in
general position
In algebraic geometry and computational geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the ''general case'' situation, as opposed to some more special or coincidental cases that ar ...
, meaning that there is a unique shortest geodesic from
to each
vertex
Vertex, vertices or vertexes may refer to:
Science and technology Mathematics and computer science
*Vertex (geometry), a point where two or more curves, lines, or edges meet
*Vertex (computer graphics), a data structure that describes the position ...
of
.
The star polygon is obtained by cutting the surface of
along these geodesics, and unfolding the resulting cut surface onto a
plane
Plane(s) most often refers to:
* Aero- or airplane, a powered, fixed-wing aircraft
* Plane (geometry), a flat, 2-dimensional surface
Plane or planes may also refer to:
Biology
* Plane (tree) or ''Platanus'', wetland native plant
* Planes (gen ...
. The resulting shape forms a
simple polygon
In geometry, a simple polygon is a polygon that does not Intersection (Euclidean geometry), intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pairwise ...
in the plane.
The star unfolding may be used as the basis for
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
algorithms for various other problems involving geodesics on convex polyhedra.
Related unfoldings
The star unfolding should be distinguished from another way of cutting a convex polyhedron into a simple polygon net, the
source unfolding In computational geometry, the source unfolding of a convex polyhedron is a net obtained by cutting the polyhedron along the cut locus of a point on the surface of the polyhedron. The cut locus of a point p consists of all points on the surface that ...
. The source unfolding cuts the polyhedron at points that have multiple equally short geodesics to the given base point
, and forms a polygon with
at its center, preserving geodesics from
. Instead, the star unfolding cuts the polyhedron along the geodesics, and forms a polygon with multiple copies of
at its vertices. Despite their names, the source unfolding always produces a
star-shaped polygon
In geometry, a star-shaped polygon is a polygonal region in the plane that is a star domain, that is, a polygon that contains a point from which the entire polygon boundary is visible.
Formally, a polygon is star-shaped if there exists a poin ...
, but the star unfolding does not.
Generalizations of the star unfolding using a geodesic or quasigeodesic in place of a single base point have also been studied. Another generalization uses a single base point, and a system of geodesics that are not necessarily shortest geodesics.
Neither the star unfolding nor the source unfolding restrict their cuts to the edges of the polyhedron. It is an open problem whether every polyhedron can be cut and unfolded to a simple polygon using only cuts along its edges.
References
{{Mathematics of paper folding
Polygons
Polyhedra
Computational geometry