|
Theta Graph
In computational geometry, the Theta graph, or \Theta-graph, is a type of geometric spanner similar to a Yao graph. The basic method of construction involves partitioning the space around each vertex into a set of ''cones'', which themselves partition the remaining vertices of the graph. Like Yao Graphs, a \Theta-graph contains at most one edge per cone; where they differ is how that edge is selected. Whereas Yao Graphs will select the nearest vertex according to the metric space of the graph, the \Theta-graph defines a fixed ray contained within each cone (conventionally the bisector of the cone) and selects the nearest neighbor with respect to orthogonal projections to that ray. The resulting graph exhibits several good spanner properties.. \Theta-graphs were first described by ClarksonK. Clarkson. 1987. Approximation algorithms for shortest path motion planning. In Proceedings of the nineteenth annual ACM symposium on Theory of computing (STOC '87), Alfred V. Aho (Ed.). ACM, ... [...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] |
Geometric Spanner
A geometric spanner or a -spanner graph or a -spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a -path between any pair of vertices for a fixed parameter . A -path is defined as a path through the graph with weight at most times the spatial distance between its endpoints. The parameter is called the stretch factor or dilation factor of the spanner. In computational geometry, the concept was first discussed by L.P. Chew in 1986, although the term "spanner" was not used in the original paper. The notion of graph spanners has been known in graph theory: -spanners are spanning subgraphs of graphs with similar dilation property, where distances between graph vertices are defined in graph-theoretical terms. Therefore geometric spanners are graph spanners of complete graphs embedded in the plane with edge weights equal to the distances between the embedded vertices in the corresponding metric. Spanners may be used in co ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Yao Graph
In computational geometry, the Yao graph, named after Andrew Yao, is a kind of geometric spanner, a weighted undirected graph connecting a set of geometric points with the property that, for every pair of points in the graph, their shortest path has a length that is within a constant factor of their Euclidean distance. The basic idea underlying the two-dimensional Yao graph is to surround each of the given points by equally spaced rays, partitioning the plane into sectors with equal angles, and to connect each point to its nearest neighbor in each of these sectors. Associated with a Yao graph is an integer parameter which is the number of rays and sectors described above; larger values of produce closer approximations to the Euclidean distance. The stretch factor is at most 1/(\cos \theta - \sin \theta), where \theta is the angle of the sectors. The same idea can be extended to point sets in more than two dimensions, but the number of sectors required grows exponentially wit ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Metric Space
In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general setting for studying many of the concepts of mathematical analysis and geometry. The most familiar example of a metric space is 3-dimensional Euclidean space with its usual notion of distance. Other well-known examples are a sphere equipped with the angular distance and the hyperbolic plane. A metric may correspond to a metaphorical, rather than physical, notion of distance: for example, the set of 100-character Unicode strings can be equipped with the Hamming distance, which measures the number of characters that need to be changed to get from one string to another. Since they are very general, metric spaces are a tool used in many different branches of mathematics. Many types of mathematical objects have a natural notion of distance and t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cambridge University Press
Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by Henry VIII of England, King Henry VIII in 1534, it is the oldest university press A university press is an academic publishing house specializing in monographs and scholarly journals. Most are nonprofit organizations and an integral component of a large research university. They publish work that has been reviewed by schola ... in the world. It is also the King's Printer. Cambridge University Press is a department of the University of Cambridge and is both an academic and educational publisher. It became part of Cambridge University Press & Assessment, following a merger with Cambridge Assessment in 2021. With a global sales presence, publishing hubs, and offices in more than 40 Country, countries, it publishes over 50,000 titles by authors from over 100 countries. Its publishing includes more than 380 academic journals, monographs, reference works, school and uni ... [...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 compl ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sweep Line Algorithm
In computational geometry, a sweep line algorithm or plane sweep algorithm is an algorithmic paradigm that uses a conceptual ''sweep line'' or ''sweep surface'' to solve various problems in Euclidean space. It is one of the key techniques in computational geometry. The idea behind algorithms of this type is to imagine that a line (often a vertical line) is swept or moved across the plane, stopping at some points. Geometric operations are restricted to geometric objects that either intersect or are in the immediate vicinity of the sweep line whenever it stops, and the complete solution is available once the line has passed over all objects. History This approach may be traced to scanline algorithms of rendering in computer graphics, followed by exploiting this approach in early algorithms of integrated circuit layout design, in which a geometric description of an IC was processed in parallel strips, because the entire description could not fit into memory. Applications Application ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Stretch Factor
The stretch factor (i.e., bilipschitz constant) of an embedding measures the factor by which the embedding distorts distances. Suppose that one metric space is embedded into another metric space by a metric map, a continuous one-to-one function that preserves or reduces the distance between every pair of points. Then the embedding gives rise to two different notions of distance between pairs of points in . Any pair of points in has both an intrinsic distance, the distance from to in , and a smaller extrinsic distance, the distance from to in . The stretch factor of the pair is the ratio between these two distances, . The stretch factor of the whole mapping is the supremum of the stretch factors of all pairs of points. The stretch factor has also been called the distortion or dilation of the mapping. The stretch factor is important in the theory of geometric spanners, weighted graphs that approximate the Euclidean distances between a set of points in the Euclidean plane ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Nearest Neighbor Graph
The nearest neighbor graph (NNG) is a directed graph defined for a set of points in a metric space, such as the Euclidean distance in the plane. The NNG has a vertex for each point, and a directed edge from ''p'' to ''q'' whenever ''q'' is a nearest neighbor of ''p'', a point whose distance from ''p'' is minimum among all the given points other than ''p'' itself. In many uses of these graphs, the directions of the edges are ignored and the NNG is defined instead as an undirected graph. However, the nearest neighbor relation is not a symmetric one, i.e., ''p'' from the definition is not necessarily a nearest neighbor for ''q''. In theoretical discussions of algorithms a kind of general position is often assumed, namely, the nearest (k-nearest) neighbor is unique for each object. In implementations of the algorithms it is necessary to bear in mind that this is not always the case. For situations in which it is necessary to make the nearest neighbor for each object unique, the set '' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computational Geometry (journal)
''Computational Geometry'', also known as ''Computational Geometry: Theory and Applications'', is a peer-reviewed mathematics journal for research in theoretical and applied computational geometry, its applications, techniques, and design and analysis of geometric algorithms. All aspects of computational geometry are covered, including the numerical, graph theoretical and combinatorial aspects, as well as fundamental problems in various areas of application of computational geometry: in computer graphics, pattern recognition, image processing, robotics, electronic design automation, CAD/CAM, and geographical information systems. The journal was founded in 1991 by Jörg-Rüdiger Sack and Jorge Urrutia.. It is indexed by ''Mathematical Reviews'', Zentralblatt MATH, Science Citation Index, and Current Contents ''Current Contents'' is a rapid alerting service database from Clarivate Analytics, formerly the Institute for Scientific Information and Thomson Reuters. It is publis ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Semi-Yao Graph
The ''k''-semi-Yao graph (''k''-SYG) of a set of ''n'' objects ''P'' is a geometric proximity graph, which was first described to present a kinetic data structure for maintenance of all the nearest neighbors on moving objects. It is named for its relation to the Yao graph, which is named after Andrew Yao. Construction The ''k''-SYG is constructed as follows. The space around each point ''p'' in ''P'' is partitioned into a set of polyhedral cones of opening angle \theta, meaning the angle of each pair of rays inside a polyhedral cone emanating from the apex is at most \theta, and then ''p'' connects to ''k'' points of ''P'' in each of the polyhedral cones whose projections on the cone axis is minimum. Properties * The ''k''-SYG, where ''k'' = 1, is known as the theta graph, and is the union of two Delaunay triangulations. * For a small \theta and an appropriate cone axis, the ''k''-SYG gives a supergraph of the ''k''-nearest neighbor graph (''k''-NNG). For example, in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
