In geometry, a polygon is a plane figure made up of line segments connected to form a closed polygonal chain.
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.
In geometry, a convex polygon is a polygon that is the boundary of a convex set. This means that the line segment between two points of the polygon is contained in the union of the interior and the boundary of the polygon. In particular, it is a simple polygon. Equivalently, a polygon is convex if every line that does not contain any edge intersects the polygon in at most two points.
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 convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.
In geometry, a set K ⊂ Rd is defined to be orthogonally convex if, for every line L that is parallel to one of standard basis vectors, the intersection of K with L is empty, a point, or a single segment. The term "orthogonal" refers to corresponding Cartesian basis and coordinates in Euclidean space, where different basis vectors are perpendicular, as well as corresponding lines. Unlike ordinary convex sets, an orthogonally convex set is not necessarily connected.
In geometry, visibility is a mathematical abstraction of the real-life notion of visibility.
Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science.
In computational geometry, the visibility polygon or visibility region for a point p in the plane among obstacles is the possibly unbounded polygonal region of all points of the plane visible from p. The visibility polygon can also be defined for visibility from a segment, or a polygon. Visibility polygons are useful in robotics, video games, and in various optimization problems such as the facility location problem and the art gallery problem.
In geometry, a polygon P in the plane is called monotone with respect to a straight line L, if every line orthogonal to L intersects the boundary of P at most twice.
The doubly connected edge list (DCEL), also known as half-edge data structure, is a data structure to represent an embedding of a planar graph in the plane, and polytopes in 3D. This data structure provides efficient manipulation of the topological information associated with the objects in question. It is used in many algorithms of computational geometry to handle polygonal subdivisions of the plane, commonly called planar straight-line graphs (PSLG). For example, a Voronoi diagram is commonly represented by a DCEL inside a bounding box.
In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain is a curve specified by a sequence of points called its vertices. The curve itself consists of the line segments connecting the consecutive vertices.
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.
In discrete geometry, an opaque set is a system of curves or other set in the plane that blocks all lines of sight across a polygon, circle, or other shape. Opaque sets have also been called barriers, beam detectors, opaque covers, or opaque forests. Opaque sets were introduced by Stefan Mazurkiewicz in 1916, and the problem of minimizing their total length was posed by Frederick Bagemihl in 1959.
In geometry, a covering of a polygon is a set of primitive units whose union equals the polygon. A polygon covering problem is a problem of finding a covering with a smallest number of units for a given polygon. This is an important class of problems in computational geometry. There are many different polygon covering problems, depending on the type of polygon being covered. An example polygon covering problem is: given a rectilinear polygon, find a smallest set of squares whose union equals the polygon.
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.
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.
In computational geometry, the source unfolding of a convex polyhedron is a net obtained by cutting the polyhedron along the cut locus of a point on the surface of the polyhedron. The cut locus of a point consists of all points on the surface that have two or more shortest geodesics to . For every convex polyhedron, and every choice of the point on its surface, cutting the polyhedron on the cut locus will produce a result that can be unfolded into a flat plane, producing the source unfolding. The resulting net may, however, cut across some of the faces of the polyhedron rather than only cutting along its edges.
