Related Research Articles
In mathematics and computational geometry, a Delaunay 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.
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.
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.
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output are random variables.
In computational geometry, polygon triangulation is the partition of a polygonal area P into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is P.
In mathematics, given a non-empty set of objects of finite extension in -dimensional space, for example a set of points, a bounding sphere, enclosing sphere or enclosing ball for that set is an -dimensional solid sphere containing all of these objects.
A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.
In computational geometry, the problem of computing the intersection of a polyhedron with a line has important applications in computer graphics, optimization, and even in some Monte Carlo methods. It can be viewed as a three-dimensional version of the line clipping problem.
The Kirkpatrick–Seidel algorithm, proposed by its authors as a potential "ultimate planar convex hull algorithm", is an algorithm for computing the convex hull of a set of points in the plane, with time complexity, where is the number of input points and is the number of points in the hull. Thus, the algorithm is output-sensitive: its running time depends on both the input size and the output size. Another output-sensitive algorithm, the gift wrapping algorithm, was known much earlier, but the Kirkpatrick–Seidel algorithm has an asymptotic running time that is significantly smaller and that always improves on the bounds of non-output-sensitive algorithms. The Kirkpatrick–Seidel algorithm is named after its inventors, David G. Kirkpatrick and Raimund Seidel.
Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science.
Cecilia Rodriguez Aragon is an American computer scientist, professor, author, and champion aerobatic pilot who is best known as the co-inventor of the treap data structure, a type of binary search tree that orders nodes by adding a priority as well as a key to each node. She is also known for her work in data-intensive science and visual analytics of very large data sets, for which she received the prestigious Presidential Early Career Award for Scientists and Engineers (PECASE).
The smallest-circle problem is a mathematical problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane. The corresponding problem in n-dimensional space, the smallest bounding sphere problem, is to compute the smallest n-sphere that contains all of a given set of points. The smallest-circle problem was initially proposed by the English mathematician James Joseph Sylvester in 1857.
In computational geometry, the method of rotating calipers is an algorithm design technique that can be used to solve optimization problems including finding the width or diameter of a set of points.
Kenneth Lee Clarkson is an American computer scientist known for his research in computational geometry. He is a researcher at the IBM Almaden Research Center, and co-editor-in-chief of the Journal of Computational Geometry.
David Galer Kirkpatrick is a Professor Emeritus of computer science at the University of British Columbia. He is known for the Kirkpatrick–Seidel algorithm and his work on polygon triangulation, and for co-inventing α-shapes and the β-skeleton. He received his PhD from the University of Toronto in 1974.
In computational geometry, an alpha shape, or α-shape, is a family of piecewise linear simple curves in the Euclidean plane associated with the shape of a finite set of points. They were first defined by Edelsbrunner, Kirkpatrick & Seidel (1983). The alpha-shape associated with a set of points is a generalization of the concept of the convex hull, i.e. every convex hull is an alpha-shape but not every alpha shape is a convex hull.
In the study of algorithms, an LP-type problem is an optimization problem that shares certain properties with low-dimensional linear programs and that may be solved by similar algorithms. LP-type problems include many important optimization problems that are not themselves linear programs, such as the problem of finding the smallest circle containing a given set of planar points. They may be solved by a combination of randomized algorithms in an amount of time that is linear in the number of elements defining the problem, and subexponential in the dimension of the problem.
Santosh Vempala is a prominent computer scientist. He is a Distinguished Professor of Computer Science at the Georgia Institute of Technology. His main work has been in the area of Theoretical Computer Science.
In computational geometry, a point p in a finite set of points S is said to be maximal or non-dominated if there is no other point q in S whose coordinates are all greater than or equal to the corresponding coordinates of p. The maxima of a point setS are all the maximal points of S. The problem of finding all maximal points, sometimes called the problem of the maxima or maxima set problem, has been studied as a variant of the convex hull and orthogonal convex hull problems. It is equivalent to finding the Pareto frontier of a collection of points, and was called the floating-currency problem by Herbert Freeman based on an application involving comparing the relative wealth of individuals with different holdings of multiple currencies.
Algorithmic Geometry is a textbook on computational geometry. It was originally written in the French language by Jean-Daniel Boissonnat and Mariette Yvinec, and published as Géometrie algorithmique by Edusciences in 1995. It was translated into English by Hervé Brönnimann, with improvements to some proofs and additional exercises, and published by the Cambridge University Press in 1998.
References
- ↑ Profile Archived 2007-10-30 at the Wayback Machine in program for conference on significant advances in computer science, Graz University of Technology, 2007.
- ↑ Seidel, Raimund (1981). A convex hull algorithm optimal for point sets in even dimensions (M. Sc.). University of British Columbia. OCLC 606375013.
- ↑ Raimund G. Seidel at the Mathematics Genealogy Project.
- ↑ Profile at the Multimodal Computing and Interaction cluster, Saarland University.
- ↑ Internationally renowned informatics center names new Scientific Director, Schloss Dagstuhl, March 30, 2014, retrieved 2014-05-06.
- ↑ Seidel, R. (1991), "Small-dimensional linear programming and convex hulls made easy", Discrete & Computational Geometry, 6 (1): 423–434, doi: 10.1007/BF02574699 .
- ↑ Aragon, Cecilia R.; Seidel, Raimund (1989), "Randomized Search Trees", Proc. 30th Symp. Foundations of Computer Science (FOCS 1989), Washington, D.C.: IEEE Computer Society Press, pp. 540–545, doi:10.1109/SFCS.1989.63531, ISBN 978-0-8186-1982-3, S2CID 47386481
- ↑ Seidel, Raimund; Aragon, Cecilia R. (1996), "Randomized Search Trees", Algorithmica, 16 (4/5): 464–497, doi:10.1007/s004539900061 .
- ↑ Kirkpatrick, David G.; Seidel, Raimund (1986), "The ultimate planar convex hull algorithm", SIAM Journal on Computing , 15 (1): 287–299, doi:10.1137/0215021, hdl: 1813/6417 .
