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.
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.
In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.
Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.
In computational geometry, polygon triangulation is the decomposition 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 geometry an arrangement of lines is the subdivision of the plane formed by a collection of lines. Bounds on the complexity of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.
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.
The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from a real-world problem of guarding an art gallery with the minimum number of guards who together can observe the whole gallery. In the geometric version of the problem, the layout of the art gallery is represented by a simple polygon and each guard is represented by a point in the polygon. A set of points is said to guard a polygon if, for every point in the polygon, there is some such that the line segment between and does not leave the polygon.
Visibility in geometry is a mathematical abstraction of the real-life notion of visibility.
In Euclidean plane geometry, a pseudotriangle (pseudo-triangle) is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A pseudotriangulation (pseudo-triangulations) is a partition of a region of the plane into pseudotriangles, and a pointed pseudotriangulation is a pseudotriangulation in which at each vertex the incident edges span an angle of less than π.
In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain P is a curve specified by a sequence of points called its vertices. The curve itself consists of the line segments connecting the consecutive vertices.
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.
Joseph O'Rourke is the Spencer T. and Ann W. Olin Professor of Computer Science at Smith College and the founding chair of the Smith computer science department. His main research interest is computational geometry.
Herbert Edelsbrunner is a computer scientist working in the field of computational geometry, the Arts & Science Professor of Computer Science and Mathematics at Duke University, Professor at the Institute of Science and Technology Austria, and the co-founder of Geomagic, Inc. He was the first of only three computer scientists to win the National Science Foundation's Alan T. Waterman Award.
In geometry, the moment curve is an algebraic curve in d-dimensional Euclidean space given by the set of points with Cartesian coordinates of the form
In geometry, the two ears theorem states that every simple polygon with more than three vertices has at least two ears, vertices that can be removed from the polygon without introducing any crossings. The two ears theorem is equivalent to the existence of polygon triangulations. It is frequently attributed to Gary H. Meisters, but was proved earlier by Max Dehn.
Geometric Folding Algorithms: Linkages, Origami, Polyhedra is a monograph on the mathematics and computational geometry of mechanical linkages, paper folding, and polyhedral nets, by Erik Demaine and Joseph O'Rourke. It was published in 2007 by Cambridge University Press (ISBN 978-0-521-85757-4). A Japanese-language translation by Ryuhei Uehara was published in 2009 by the Modern Science Company (ISBN 978-4-7649-0377-7).
Combinatorial Geometry in the Plane is a book in discrete geometry. It was translated from a German-language book, Kombinatorische Geometrie in der Ebene, which its authors Hugo Hadwiger and Hans Debrunner published through the University of Geneva in 1960, expanding a 1955 survey paper that Hadwiger had published in L'Enseignement mathématique. Victor Klee translated it into English, and added a chapter of new material. It was published in 1964 by Holt, Rinehart and Winston, and republished in 1966 by Dover Publications. A Russian-language edition, Комбинаторная геометрия плоскости, translated by I. M. Jaglom and including a summary of the new material by Klee, was published by Nauka in 1965. The Basic Library List Committee of the Mathematical Association of America has recommended its inclusion in undergraduate mathematics libraries.
