|
Point Set Triangulation
A triangulation of a set of points \mathcal in the Euclidean space \mathbb^d is a simplicial complex that covers the convex hull of \mathcal, and whose vertices belong to \mathcal. In the plane (when \mathcal is a set of points in \mathbb^2), triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of \mathcal are vertices of its triangulations. In this case, a triangulation of a set of points \mathcal in the plane can alternatively be defined as a maximal set of non-crossing edges between points of \mathcal. In the plane, triangulations are special cases of planar straight-line graphs. A particularly interesting kind of triangulations are the Delaunay triangulations. They are the geometric duals of Voronoi diagrams. The Delaunay triangulation of a set of points \mathcal in the plane contains the Gabriel graph, the nearest neighbor graph and the minimal spanning tree of \mathcal. Triangulations have a number of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no". # When the answer is "yes", this can be demonstrated through the existence of a short (polynomial length) ''solution''. # The correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions. # The problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. Hence, if we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified. The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Triangulation (geometry)
In geometry, a triangulation is a subdivision of a plane (geometry), planar object into triangles, and by extension the subdivision of a higher-dimension geometric object into simplex, simplices. Triangulations of a three-dimensional volume would involve subdividing it into tetrahedra packed together. In most instances, the triangles of a triangulation are required to meet edge-to-edge and vertex-to-vertex. Types Different types of triangulations may be defined, depending both on what geometric object is to be subdivided and on how the subdivision is determined. * A triangulation T of \mathbb^d is a subdivision of \mathbb^d into d-dimensional simplices such that any two simplices in T intersect in a common face (a simplex of any lower dimension) or not at all, and any bounded set in \mathbb^d intersects only finite set, finitely many simplices in T. That is, it is a locally finite simplicial complex that covers the entire space. * A point-set triangulation, i.e., a triangulation ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Discrete And 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'' Notable articles Two articles published in ''Discrete & Computational Geometry'', one by Gil Kalai in 1992 with a proof of a subexponential upper bound on the diameter of a polytope and another by Samuel Ferguson in 2006 on the Kepler conjecture on optimal three-dimensional sphere packing, earned their authors 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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polygon Triangulation
In computational geometry, polygon triangulation is the partition of a polygonal area (simple polygon) into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is . Triangulations may be viewed as special cases of planar straight-line graphs. When there are no holes or added points, triangulations form maximal outerplanar graphs. Polygon triangulation without extra vertices Over time, a number of algorithms have been proposed to triangulate a polygon. Special cases It is trivial to triangulate any convex polygon in linear time into a fan triangulation, by adding diagonals from one vertex to all other non-nearest neighbor vertices. The total number of ways to triangulate a convex ''n''-gon by non-intersecting diagonals is the (''n''−2)nd Catalan number, which equals :\frac, a formula found by Leonhard Euler. A monotone polygon can be triangulated in linear time with either the algorithm of A. Fournier ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mesh Generation
Mesh generation is the practice of creating a polygon mesh, mesh, a subdivision of a continuous geometric space into discrete geometric and topological cells. Often these cells form a simplicial complex. Usually the cells partition the geometric input domain. Mesh cells are used as discrete local approximations of the larger domain. Meshes are created by computer algorithms, often with human guidance through a GUI, depending on the complexity of the domain and the type of mesh desired. A typical goal is to create a mesh that accurately captures the input domain geometry, with high-quality (well-shaped) cells, and without so many cells as to make subsequent calculations intractable. The mesh should also be fine (have small elements) in areas that are important for the subsequent calculations. Meshes are used for rendering (computer graphics), rendering to a computer screen and for physical simulation such as finite element analysis or computational fluid dynamics. Meshes are compo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Minimum-weight Triangulation
In computational geometry and computer science, the minimum-weight triangulation problem is the problem of finding a triangulation of minimal total edge length. That is, an input polygon or the convex hull of an input point set must be subdivided into triangles that meet edge-to-edge and vertex-to-vertex, in such a way as to minimize the sum of the perimeters of the triangles. The problem is NP-hard for point set inputs, but may be approximated to any desired degree of accuracy. For polygon inputs, it may be solved exactly in polynomial time. The minimum weight triangulation has also sometimes been called the optimal triangulation. History The problem of minimum weight triangulation of a point set was posed by , who suggested its application to the construction of triangulated irregular network models of land countours, and used a greedy heuristic to approximate it. conjectured that the minimum weight triangulation always coincided with the Delaunay triangulation, but this was q ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP-hard
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assuming a solution for ''H'' takes 1 unit time, ''H''s solution can be used to solve ''L'' in polynomial time. As a consequence, finding a polynomial time algorithm to solve a single NP-hard problem would give polynomial time algorithms for all the problems in the complexity class NP. As it is suspected, but unproven, that P≠NP, it is unlikely that any polynomial-time algorithms for NP-hard problems exist. A simple example of an NP-hard problem is the subset sum problem. Informally, if ''H'' is NP-hard, then it is at least as difficult to solve as the problems in NP. However, the opposite direction is not true: some problems are undecidable, and therefore even more difficult to solve than all problems in NP, but they are probably not NP- ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Convex Hull Algorithms
Algorithms that construct convex hulls of various objects have a Convex hull#Applications, broad range of applications in mathematics and computer science. In computational geometry, numerous algorithms are proposed for computing the convex hull of a finite set of points, with various Analysis of algorithms, computational complexities. Computing the convex hull means that a non-ambiguous and efficient data structure, representation of the required convex shape is constructed. The complexity of the corresponding algorithms is usually estimated in terms of ''n'', the number of input points, and sometimes also in terms of ''h'', the number of points on the convex hull. Planar case Consider the general case when the input to the algorithm is a finite unordered set of points on a Cartesian plane. An important special case, in which the points are given in the order of traversal of a simple polygon's boundary, is described later in a separate subsection. If not all points are on the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Euler Characteristic
In mathematics, and more specifically in algebraic topology and polyhedral combinatorics, the Euler characteristic (or Euler number, or Euler–Poincaré characteristic) is a topological invariant, a number that describes a topological space's shape or structure regardless of the way it is bent. It is commonly denoted by \chi (Greek alphabet, Greek lower-case letter chi (letter), chi). The Euler characteristic was originally defined for polyhedron, polyhedra and used to prove various theorems about them, including the classification of the Platonic solids. It was stated for Platonic solids in 1537 in an unpublished manuscript by Francesco Maurolico. Leonhard Euler, for whom the concept is named, introduced it for convex polyhedra more generally but failed to rigorously prove that it is an invariant. In modern mathematics, the Euler characteristic arises from homology (mathematics), homology and, more abstractly, homological algebra. Polyhedra The Euler characteristic was ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Simplicial Polytope
In geometry, a simplicial polytope is a polytope whose facet_(mathematics), facets are all Simplex, simplices. For example, a ''simplicial polyhedron'' in three dimensions contains only Triangle, triangular faces (p.341) and corresponds via Steinitz's theorem to a maximal planar graph. They are Dual_polyhedron#Topological_duality, topologically dual to simple polytopes. Polytopes which are both simple and simplicial are either simplices or two-dimensional polygons. Examples Simplicial polyhedra include: * Bipyramids * Gyroelongated bipyramids *Deltahedron, Deltahedra (equilateral triangles) ** Platonic solid, Platonic *** tetrahedron, octahedron, icosahedron ** Johnson solids: ***triangular bipyramid, pentagonal bipyramid, snub disphenoid, triaugmented triangular prism, ...[...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
