In geometry, the convex hull, 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.
Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph, or a minimum spanning forest in the case of a graph that is not connected.
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.
Philippe Flajolet was a French computer scientist.
In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a piecewise-linear Jordan curve consisting of finitely many line segments. These polygons include as special cases the convex polygons, star-shaped polygons, and monotone polygons.
A triangulation of a set of points in the Euclidean space is a simplicial complex that covers the convex hull of , and whose vertices belong to . In the plane, triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of are vertices of its triangulations. In this case, a triangulation of a set of points in the plane can alternatively be defined as a maximal set of non-crossing edges between points of . In the plane, triangulations are special cases of planar straight-line graphs.
In mathematics, discrepancy theory describes the deviation of a situation from the state one would like it to be in. It is also called the theory of irregularities of distribution. This refers to the theme of classical discrepancy theory, namely distributing points in some space such that they are evenly distributed with respect to some subsets. The discrepancy (irregularity) measures how far a given distribution deviates from an ideal one.
Otakar Borůvka was a Czech mathematician best known today for his work in graph theory.
Godfried Theodore Patrick Toussaint was a Canadian computer scientist, a professor of computer science, and the head of the Computer Science Program at New York University Abu Dhabi (NYUAD) in Abu Dhabi, United Arab Emirates. He is considered to be the father of computational geometry in Canada. He did research on various aspects of computational geometry, discrete geometry, and their applications: pattern recognition, motion planning, visualization, knot theory, linkage (mechanical) reconfiguration, the art gallery problem, polygon triangulation, the largest empty circle problem, unimodality, and others. Other interests included meander (art), compass and straightedge constructions, instance-based learning, music information retrieval, and computational music theory.
Kurt Mehlhorn is a German theoretical computer scientist. He has been a vice president of the Max Planck Society and is director of the Max Planck Institute for Computer Science.
János Pach is a mathematician and computer scientist working in the fields of combinatorics and discrete and computational geometry.
WADS, the Algorithms and Data Structures Symposium, is an international academic conference in the field of computer science, focusing on algorithms and data structures. WADS is held every second year, usually in Canada and always in North America. It is held in alternation with its sister conference, the Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), which is usually held in Scandinavia and always in Northern Europe. Historically, the proceedings of both conferences were published by Springer Verlag through their Lecture Notes in Computer Science series. Springer continues to publish WADS proceedings, but starting in 2016, SWAT proceedings are now published by Dagstuhl through their Leibniz International Proceedings in Informatics.
Pankaj Kumar Agarwal is an Indian computer scientist and mathematician researching algorithms in computational geometry and related areas. He is the RJR Nabisco Professor of Computer Science and Mathematics at Duke University, where he has been chair of the computer science department since 2004. He obtained his Doctor of Philosophy (Ph.D.) in computer science in 1989 from the Courant Institute of Mathematical Sciences, New York University, under the supervision of Micha Sharir.
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.
In geometry, a partition of a polygon is a set of primitive units, which do not overlap and whose union equals the polygon. A polygon partition problem is a problem of finding a partition which is minimal in some sense, for example a partition with a smallest number of units or with units of smallest total side-length.
Monique Teillaud is a French researcher in computational geometry at the French Institute for Research in Computer Science and Automation (INRIA) in Nancy, France. She moved to Nancy in 2014 from a different INRIA center in Sophia Antipolis, where she was one of the developers of CGAL, a software library of computational geometry algorithms.
In discrete geometry and computational geometry, the relative convex hull or geodesic convex hull is an analogue of the convex hull for the points inside a simple polygon or a rectifiable simple closed curve.
In computational geometry, a polygonalization of a finite set of points in the Euclidean plane is a simple polygon with the given points as its vertices. A polygonalization may also be called a polygonization, simple polygonalization, Hamiltonian polygon, non-crossing Hamiltonian cycle, or crossing-free straight-edge spanning cycle.
