|
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 have two or more shortest geodesics to p. For every convex polyhedron, and every choice of the point p on its surface, cutting the polyhedron on the cut locus will produce a result that can be unfolded into a flat plane, producing the source unfolding. The resulting net may, however, cut across some of the faces of the polyhedron rather than only cutting along its edges. The source unfolding can also be continuously transformed from the polyhedron to its flat net, keeping flat the parts of the net that do not lie along edges of the polyhedron, as a blooming of the polyhedron. The unfolded shape of the source unfolding is always a star-shaped polygon, with all of its points visible by straight line segments from the image of p; this is in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity. Analysis of algorithms, Computational complexity is central to computational geometry, with great practical significance if algorithms are used on very large datasets containing tens or hundreds of millions of points. For such sets, the difference between O(''n''2) and O(''n'' log ''n'') may be the difference between days and seconds of computation. The main impetus for the development of computational geometry as a discipline was progress in computer graphics and computer-aided design and manufacturing (Computer-aided design, CAD/Compu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 word "polyhedron" for the more general, possibly unbounded object. Others''Mathematical Programming'', by Melvyn W. Jeter (1986) p. 68/ref> (including this article) allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary. Convex polytopes play an important role both in various branches of mathematics and in applied areas, most notably in linear programming. In the influential textbooks of Grünbaum and Ziegler on the subject, as well as in many other texts in discrete geometry, convex polytopes are often simply called "polytopes". Grünbaum points out that this is solely to avoi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Net (polyhedron)
In geometry, a net of a polyhedron is an arrangement of non-overlapping edge-joined polygons in the plane which can be folded (along edges) to become the faces of the polyhedron. Polyhedral nets are a useful aid to the study of polyhedra and solid geometry in general, as they allow for physical models of polyhedra to be constructed from material such as thin cardboard. An early instance of polyhedral nets appears in the works of Albrecht Dürer, whose 1525 book ''A Course in the Art of Measurement with Compass and Ruler'' (''Unterweysung der Messung mit dem Zyrkel und Rychtscheyd '') included nets for the Platonic solids and several of the Archimedean solids. These constructions were first called nets in 1543 by Augustin Hirschvogel. Existence and uniqueness Many different nets can exist for a given polyhedron, depending on the choices of which edges are joined and which are separated. The edges that are cut from a convex polyhedron to form a net must form a spanning tree of t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cut Locus
The cut locus is a mathematical structure defined for a closed set S in a space X as the closure of the set of all points p\in X that have two or more distinct shortest paths in X from S to p. Definition in a special case Let X be a metric space, equipped with the metric \mathrm_X, and let x \in X be a point. The cut locus of x in X (\operatorname_X(x)), is the locus of all the points in X for which there exists at least two distinct shortest paths to x in X. More formally, y \in \operatorname_X(x) for a point y in X if and only if there exists two paths \gamma,\gamma':I\to X such that \gamma(0) = \gamma'(0) = x, \gamma(1)=\gamma'(1)=y, , \gamma, =, \gamma', = \mathrm_X(x,y), and the trajectories of the two paths are distinct. Examples For example, let ''S'' be the boundary of a simple polygon, and ''X'' the interior of the polygon. Then the cut locus is the medial axis of the polygon. The points on the medial axis are centers of maximal disks that touch the polygon bounda ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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. It is a generalization of the notion of a "straight line". The noun '' geodesic'' and the adjective ''geodetic'' come from ''geodesy'', the science of measuring the size and shape of Earth, though many of the underlying principles can be applied to any ellipsoidal geometry. In the original sense, a geodesic was the shortest route between two points on the Earth's surface. For a spherical Earth, it is a segment of a great circle (see also great-circle distance). The term has since been generalized to more abstract mathematical spaces; for example, in graph theory, one might consider a geodesic between two vertices/nodes of a graph. In a Riemannian manifold or submanifold, geodesics are characterised by the property of having vanishin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Blooming (geometry)
In the geometry of convex polyhedra, blooming or continuous blooming is a continuous three-dimensional motion of the surface of the polyhedron, cut to form a polyhedral net, from the polyhedron into a flat and non-self-overlapping placement of the net in a plane. As in rigid origami, the polygons of the net must remain individually flat throughout the motion, and are not allowed to intersect or cross through each other. A blooming, reversed to go from the flat net to a polyhedron, can be thought of intuitively as a way to fold the polyhedron from a paper net without bending the paper except at its designated creases. An early work on blooming by Biedl, Lubiw, and Sun from 1999 showed that some nets for non-convex but topologically spherical polyhedra have no blooming. The question of whether every convex polyhedron admits a net with a blooming was posed by Robert Connelly, and came to be known as Connelly’s blooming conjecture. More specifically, Miller and Pak suggested in 200 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 point such that for each point of the segment lies entirely within . The set of all points with this property (that is, the set of points from which all of is visible) is called the kernel of . If a star-shaped polygon is convex, the link distance between any two of its points (the minimum number of sequential line segments sufficient to connect those points) is 1, and so the polygon's link diameter (the maximum link distance over all pairs of points) is 1. If a star-shaped polygon is not convex, the link distance between a point in the kernel and any other point in the polygon is 1, while the link distance between any two points that are in the polygon but outside the kernel is either 1 or 2; in this case the maximum link distance is 2. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Star Unfolding
In computational geometry, the star unfolding of a convex polyhedron is a net obtained by cutting the polyhedron along geodesics (shortest paths) through its faces. It has also been called the inward layout of the polyhedron, or the Alexandrov unfolding after Aleksandr Danilovich Aleksandrov, who first considered it. Description In more detail, the star unfolding is obtained from a polyhedron P by choosing a starting point p on the surface of P, in general position, meaning that there is a unique shortest geodesic from p to each vertex of P. The star polygon is obtained by cutting the surface of P along these geodesics, and unfolding the resulting cut surface onto a plane. The resulting shape forms a simple polygon in the plane. The star unfolding may be used as the basis for polynomial time 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 int ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Convex Polytope
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 word "polyhedron" for the more general, possibly unbounded object. Others''Mathematical Programming'', by Melvyn W. Jeter (1986) p. 68/ref> (including this article) allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary. Convex polytopes play an important role both in various branches of mathematics and in applied areas, most notably in linear programming. In the influential textbooks of Grünbaum and Ziegler on the subject, as well as in many other texts in discrete geometry, convex polytopes are often simply called "polytopes". Grünbaum points out that this is solely to avoi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hyperplane
In geometry, a hyperplane is a subspace whose dimension is one less than that of its ''ambient space''. For example, if a space is 3-dimensional then its hyperplanes are the 2-dimensional planes, while if the space is 2-dimensional, its hyperplanes are the 1-dimensional lines. This notion can be used in any general space in which the concept of the dimension of a subspace is defined. In different settings, hyperplanes may have different properties. For instance, a hyperplane of an -dimensional affine space is a flat subset with dimension and it separates the space into two half spaces. While a hyperplane of an -dimensional projective space does not have this property. The difference in dimension between a subspace and its ambient space is known as the codimension of with respect to . Therefore, a necessary and sufficient condition for to be a hyperplane in is for to have codimension one in . Technical description In geometry, a hyperplane of an ''n''-dimensi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graphs And Combinatorics
''Graphs and Combinatorics'' (ISSN 0911-0119, abbreviated ''Graphs Combin.'') is a peer-reviewed academic journal in graph theory, combinatorics, and discrete geometry published by Springer Japan. Its editor-in-chief is Katsuhiro Ota of Keio University. The journal was first published in 1985. Its founding editor in chief was Hoon Heng Teh of Singapore, the president of the Southeast Asian Mathematics Society, and its managing editor was Jin Akiyama. Originally, it was subtitled "An Asian Journal". In most years since 1999, it has been ranked as a second-quartile journal in discrete mathematics and theoretical computer science computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the ... by SCImago Journal Rank.. References {{reflist Publications established in 1985 Combinatorics jo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Discrete & Computational Geometry
'' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational geometry. Abstracting and indexing The journal is indexed in: * ''Mathematical Reviews'' * ''Zentralblatt MATH'' * ''Science Citation Index'' * ''Current Contents''/Engineering, Computing and Technology Notable articles The articles by Gil Kalai with a proof of a subexponential upper bound on the diameter of a polyhedron and by Samuel Ferguson on the Kepler conjecture, both published in Discrete & Computational geometry, earned their author the Fulkerson Prize The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at e .... References External link ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
