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 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.
Let be a simple polygon or a rectifiable simple closed curve, and let be any set enclosed by . A geodesic between two points in is a shortest path connecting those two points that stays entirely within . A subset of the points inside is said to be relatively convex, geodesically convex, or -convex if, for every two points of , the geodesic between them in stays within . Then the relative convex hull of can be defined as the intersection of all relatively convex sets containing . [1]
Equivalently, the relative convex hull is the minimum-perimeter weakly simple polygon in that encloses . This was the original formulation of relative convex hulls, by Sklansky, Chazin & Hansen (1972). [2] However this definition is complicated by the need to use weakly simple polygons (intuitively, polygons in which the polygon boundary can touch or overlap itself but not cross itself) instead of simple polygons when is disconnected and its components are not all visible to each other.
Toussaint (1986), who provided an efficient algorithm for the construction of the relative convex hull for finite sets of points inside a simple polygon. [3] With subsequent improvements in the time bounds for two subroutines, finding shortest paths between query points in a polygon, [4] and polygon triangulation, [5] this algorithm takes time on an input with points in a polygon with vertices. [4] It can also be maintained dynamically in sublinear time per update. [6]
The relative convex hull of a finite set of points is always a weakly simple polygon, but it might not actually be a simple polygon, because parts of it can be connected to each other by line segments or polygonal paths rather than by regions of nonzero area.
For relative convex hulls of simple polygons, an alternative but equivalent definition of convexity can be used. A simple polygon within another simple polygon is relatively convex or -convex if every line segment contained in that connects two points of lies within . The relative convex hull of a simple polygon within can be defined as the intersection of all -convex polygons that contain , as the smallest -convex polygon that contains , or as the minimum-perimeter simple polygon that contains and is contained by . [1]
Klette (2010) generalizes linear time algorithms for the convex hull of a simple polygon to the relative convex hull of one simple polygon within another. The resulting generalized algorithm is not linear time, however: its time complexity depends on the depth of nesting of certain features of one polygon within another. In this case, the relative convex hull is itself a simple polygon. [1] Alternative linear time algorithms based on path planning are known. [7]
A similar definition can also be given for the relative convex hull of two disjoint simple polygons. This type of hull can be used in algorithms for testing whether the two polygons can be separated into disjoint halfplanes by a continuous linear motion, [8] and in data structures for collision detection of moving polygons. [9]
The definition of relative convex hulls based on minimum enclosure does not extend to higher dimensions, because (even without being surrounded by an outer shape) the minimum surface area enclosure of a non-convex set is not generally convex. [7] However, for the relative convex hull of a connected set within another set, a similar definition to one for simple polygons can be used. In this case, a relatively convex set can again be defined as a subset of the given outer set that contains all line segments in the outer set between pairs of its points. The relative convex hull can be defined as the intersection of all relatively convex sets that contain the inner set. [10]
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.
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.
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 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.
The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from the following real-world problem:
"In an art gallery, what is the minimum number of guards who together can observe the whole gallery?"
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.
The Euclidean shortest path problem is a problem in computational geometry: given a set of polyhedral obstacles in a Euclidean space, and two points, find the shortest path between the points that does not intersect any of the obstacles.
The dynamic convex hull problem is a class of dynamic problems in computational geometry. The problem consists in the maintenance, i.e., keeping track, of the convex hull for input data undergoing a sequence of discrete changes, i.e., when input data elements may be inserted, deleted, or modified. It should be distinguished from the kinetic convex hull, which studies similar problems for continuously moving points. Dynamic convex hull problems may be distinguished by the types of the input data and the allowed types of modification of the input data.
Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science.
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.
In geometry, the minimum bounding box or smallest bounding box for a point set S in N dimensions is the box with the smallest measure within which all the points lie. When other kinds of measure are used, the minimum box is usually called accordingly, e.g., "minimum-perimeter bounding box".
In computational geometry, the relative neighborhood graph (RNG) is an undirected graph defined on a set of points in the Euclidean plane by connecting two points and by an edge whenever there does not exist a third point that is closer to both and than they are to each other. This graph was proposed by Godfried Toussaint in 1980 as a way of defining a structure from a set of points that would match human perceptions of the shape of the set.
In differential geometry, the cut locus of a point p on a manifold is the closure of the set of all other points on the manifold that are connected to p by two or more distinct shortest geodesics. More generally, the cut locus of a closed set X on the manifold is the closure of the set of all other points on the manifold connected to X by two or more distinct shortest geodesics.
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 computational geometry, a constrained Delaunay triangulation is a generalization of the Delaunay triangulation that forces certain required segments into the triangulation as edges, unlike the Delaunay triangulation itself which is based purely on the position of a given set of vertices without regard to how they should be connected by edges. It can be computed efficiently and has applications in geographic information systems and in mesh generation.
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.
In discrete geometry and computational geometry, the convex hull of a simple polygon is the polygon of minimum perimeter that contains a given simple polygon. It is a special case of the more general concept of a convex hull. It can be computed in linear time, faster than algorithms for convex hulls of point sets.
In computational geometry, the star unfolding of a convex polyhedron is a net obtained by cutting the polyhedron along geodesics through its faces. It has also been called the inward layout of the polyhedron, or the Alexandrov unfolding after Aleksandr Danilovich Aleksandrov, who first considered it.
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.
