|
Pitteway Triangulation
In computational geometry, a Pitteway triangulation is a point set triangulation in which the nearest neighbor of any point ''p'' within the triangulation is one of the vertices of the triangle containing ''p''. Alternatively, it is a Delaunay triangulation in which each internal edge crosses its dual Voronoi diagram edge. Pitteway triangulations are named after Michael Pitteway, who studied them in 1973. Not every point set supports a Pitteway triangulation. When such a triangulation exists it is a special case of the Delaunay triangulation, and consists of the union of the Gabriel graph and convex hull. History The concept of a Pitteway triangulation was introduced by . See also , who writes "An optimal partition is one in which, for any point within any triangle, that point lies at least as close to one of the vertices of that triangle as to any other data point." The name "Pitteway triangulation" was given by . Counterexamples points out that not every point set supports ... [...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. 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 (CAD/CAM), but many problems in computational geometry ar ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Nearest Neighbor Search
Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically expressed in terms of a dissimilarity function: the less similar the objects, the larger the function values. Formally, the nearest-neighbor (NN) search problem is defined as follows: given a set ''S'' of points in a space ''M'' and a query point ''q'' ∈ ''M'', find the closest point in ''S'' to ''q''. Donald Knuth in vol. 3 of ''The Art of Computer Programming'' (1973) called it the post-office problem, referring to an application of assigning to a residence the nearest post office. A direct generalization of this problem is a ''k''-NN search, where we need to find the ''k'' closest points. Most commonly ''M'' is a metric space and dissimilarity is expressed as a distance metric, which is symmetric and satisfies the triangle inequality. Even more common, ''M'' is taken ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Delaunay Triangulation
In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position 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 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. For a set of points on the same line there is no Delaunay triangulation (the notion of triangulation is degenerate for this case). For four or more points on the same circle (e.g., the vertices of a rectangle) the Delaunay triangulation is not unique: each of the two possible triangulations that split the quadrangle into two triangles satisfies the "Delaunay condition", i.e., the requirement that the circumcircles of all triangles have empty interiors. By considering circumscribed spheres ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Dual Graph
In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge of has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of . The definition of the dual depends on the choice of embedding of the graph , so it is a property of plane graphs (graphs that are already embedded in the plane) rather than planar graphs (graphs that may be embedded but for which the embedding is not yet known). For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph. Historically, the first form of graph duality to be recognized was the association of the Platonic solids into pairs of dual polyhedra. Graph duality is a topological ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Voronoi Diagram
In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed there is a corresponding region, called a Voronoi cell, consisting of all points of the plane closer to that seed than to any other. The Voronoi diagram of a set of points is dual to that set's Delaunay triangulation. The Voronoi diagram is named after mathematician Georgy Voronoy, and is also called a Voronoi tessellation, a Voronoi decomposition, a Voronoi partition, or a Dirichlet tessellation (after Peter Gustav Lejeune Dirichlet). Voronoi cells are also known as Thiessen polygons. Voronoi diagrams have practical and theoretical applications in many fields, mainly in science and technology, but also in visual art. The simplest case In the simplest case, shown in the first picture, we are given a finite set of points in the Euclidean ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Gabriel Graph
In mathematics and computational geometry, the Gabriel graph of a set S of points in the Euclidean plane expresses one notion of proximity or nearness of those points. Formally, it is the graph G with vertex set S in which any two distinct points p \in S and q \in S are adjacent precisely when the closed disc having pq as a diameter contains no other points. Another way of expressing the same adjacency criterion is that p and q should be the two closest given points to their midpoint, with no other given point being as close. Gabriel graphs naturally generalize to higher dimensions, with the empty disks replaced by empty closed balls. Gabriel graphs are named after K. Ruben Gabriel, who introduced them in a paper with Robert R. Sokal in 1969. Percolation For Gabriel graphs of infinite random point sets, the finite site percolation threshold gives the fraction of points needed to support connectivity: if a random subset of fewer vertices than the threshold is given, the re ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Convex Hull
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset. Convex hulls of open sets are open, and convex hulls of compact sets are compact. Every compact convex set is the convex hull of its extreme points. The convex hull operator is an example of a closure operator, and every antimatroid can be represented by applying this closure operator to finite sets of points. The algorithmic problems of finding the convex hull of a finite set of points in the plane or other low-dimensional Euclidean spaces, and its dual problem of intersecting half-spaces, are fundamental problems ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Regular Pentagon
In geometry, a pentagon (from the Greek πέντε ''pente'' meaning ''five'' and γωνία ''gonia'' meaning ''angle'') is any five-sided polygon or 5-gon. The sum of the internal angles in a simple pentagon is 540°. A pentagon may be simple or self-intersecting. A self-intersecting ''regular pentagon'' (or ''star pentagon'') is called a pentagram. Regular pentagons A ''regular polygon, regular pentagon'' has Schläfli symbol and interior angles of 108°. A ''regular polygon, regular pentagon'' has five lines of reflectional symmetry, and rotational symmetry of order 5 (through 72°, 144°, 216° and 288°). The diagonals of a convex polygon, convex regular pentagon are in the golden ratio to its sides. Given its side length t, its height H (distance from one side to the opposite vertex), width W (distance between two farthest separated points, which equals the diagonal length D) and circumradius R are given by: :\begin H &= \frac~t \approx 1.539~t, \\ W= ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Isosceles Triangle
In geometry, an isosceles triangle () is a triangle that has two sides of equal length. Sometimes it is specified as having ''exactly'' two sides of equal length, and sometimes as having ''at least'' two sides of equal length, the latter version thus including the equilateral triangle as a special case. Examples of isosceles triangles include the isosceles right triangle, the golden triangle, and the faces of bipyramids and certain Catalan solids. The mathematical study of isosceles triangles dates back to ancient Egyptian mathematics and Babylonian mathematics. Isosceles triangles have been used as decoration from even earlier times, and appear frequently in architecture and design, for instance in the pediments and gables of buildings. The two equal sides are called the legs and the third side is called the base of the triangle. The other dimensions of the triangle, such as its height, area, and perimeter, can be calculated by simple formulas from the lengths of the l ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 are possible, which is referred to as special position. Its precise meaning differs in different settings. For example, generically, two lines in the plane intersect in a single point (they are not parallel or coincident). One also says "two generic lines intersect in a point", which is formalized by the notion of a generic point. Similarly, three generic points in the plane are not collinear; if three points are collinear (even stronger, if two coincide), this is a degenerate case. This notion is important in mathematics and its applications, because degenerate cases may require an exceptional treatment; for example, when stating general theorems or giving precise statements thereof, and when writing computer programs (see '' generic co ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
