Quasi-triangulation

Last updated

A quasi-triangulation is a subdivision of a geometric object into simplices, where vertices are not points but arbitrary sloped line segments. [1] This division is not a triangulation in the geometric sense. It is a topological triangulation, however. A quasi-triangulation may have some of the characteristics of a Delaunay triangulation.

In geometry, a triangulation is a subdivision of a planar object into triangles, and by extension the subdivision of a higher-dimension geometric object into simplices. Triangulations of a three-dimensional volume would involve subdividing it into tetrahedra packed together.

Triangulation (topology)

In mathematics, topology generalizes the notion of triangulation in a natural way as follows:

Delaunay triangulation

In mathematics and computational geometry, a Delaunay triangulation for a given set P of discrete points in a plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation; they tend to avoid sliver triangles. The triangulation is named after Boris Delaunay for his work on this topic from 1934.

Quasi-triangulation. Line segments of the topology (quasi-vertices) are shown in black, gray -- quasi-edges, white -- faces. a -- a convex quadrangular edge, b -- a nonconvex quadrangular edge, c -- a triangular edge, d -- a degenerate edge, a and e -- parallel edges, f -- a quasi-edge contains a part of the line segment. Quasitriangulation.png
Quasi-triangulation. Line segments of the topology (quasi-vertices) are shown in black, gray — quasi-edges, white — faces. a — a convex quadrangular edge, b — a nonconvex quadrangular edge, c — a triangular edge, d — a degenerate edge, a and e — parallel edges, f — a quasi-edge contains a part of the line segment.

Related Research Articles

Geometric distribution probability distribution

In probability theory and statistics, the geometric distribution is either of two discrete probability distributions:

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 history stretching back to antiquity.

Algebraic variety object of study in algebraic geometry

Algebraic varieties are the central objects of study in algebraic geometry. Classically, an algebraic variety is defined as the set of solutions of a system of polynomial equations over the real or complex numbers. Modern definitions generalize this concept in several different ways, while attempting to preserve the geometric intuition behind the original definition.

In mathematics, in particular in the theory of schemes in algebraic geometry, a flat morphismf from a scheme X to a scheme Y is a morphism such that the induced map on every stalk is a flat map of rings, i.e.,

In mathematics, especially in algebraic geometry and the theory of complex manifolds, coherent sheaves are a class of sheaves closely linked to the geometric properties of the underlying space. The definition of coherent sheaves is made with reference to a sheaf of rings that codifies this geometric information.

In mathematics, a hyperbolic metric space is a metric space satisfying certain metric relations between points. The definition, introduced by Mikhael Gromov, generalizes the metric properties of classical hyperbolic geometry and of trees. Hyperbolicity is a large-scale property, and is very useful to the study of certain infinite groups called (Gromov-)hyperbolic groups.

In mathematics, the Teichmüller space of a (real) topological surface , is a space that parametrizes complex structures on up to the action of homeomorphisms that are isotopic to the identity homeomorphism. Each point in may be regarded as an isomorphism class of "marked" Riemann surfaces, where a "marking" is an isotopy class of homeomorphisms from to itself.

Hyperbolic group

In group theory, more precisely in geometric group theory, a hyperbolic group, also known as a word hyperbolic group or Gromov hyperbolic group, is a finitely generated group equipped with a word metric satisfying certain properties abstracted from classical hyperbolic geometry. The notion of a hyperbolic group was introduced and developed by Mikhail Gromov (1987). The inspiration came from various existing mathematical theories: hyperbolic geometry but also low-dimensional topology, and combinatorial group theory. In a very influential chapter from 1987, Gromov proposed a wide-ranging research program. Ideas and foundational material in the theory of hyperbolic groups also stem from the work of George Mostow, William Thurston, James W. Cannon, Eliyahu Rips, and many others.

Geometric graph theory

Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geometric graphs, meaning graphs drawn in the Euclidean plane with possibly intersecting straight-line edges, and topological graphs, where the edges are allowed to be arbitrary continuous curves connecting the vertices, thus it is "the theory of geometric and topological graphs".

In mathematics, specifically geometric group theory, a geometric group action is a certain type of action of a discrete group on a metric space.

Quasi-isometry

In mathematics, quasi-isometry is an equivalence relation on metric spaces that ignores their small-scale details in favor of their coarse structure. The concept is especially important in geometric group theory following the work of Gromov.

In computer vision triangulation refers to the process of determining a point in 3D space given its projections onto two, or more, images. In order to solve this problem it is necessary to know the parameters of the camera projection function from 3D to 2D for the cameras involved, in the simplest case represented by the camera matrices. Triangulation is sometimes also referred to as reconstruction.

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.

This is a glossary of algebraic geometry.

Surface triangulation

Triangulation of a surface means

Flip graph

A flip graph is a graph whose vertices are combinatorial or geometric objects, and whose edges link two of these objects when they can be obtained from one another by an elementary operation called a flip. Flip graphs are special cases of geometric graphs.

References

  1. Luzin S.Y.; Lyachek Y.T.; Petrosyan G.S.; Polubasov O.B. (2010). Models and algorithms for automated design of electronic and computer equipment (in Russian). BHV-Petersburg. p. 224. ISBN   978-5-9775-0576-5.