List of combinatorial computational geometry topics
Encyclopedia
List of combinatorial computational geometry topics enumerates the topics of computational geometry
that states problems in terms of geometric objects as discrete
entities and hence the methods of their solution are mostly theories and algorithm
s of combinatorial
character.
See List of numerical computational geometry topics for another flavor of computational geometry that deals with geometric objects as continuous entities and applies methods and algorithms of nature characteristic to numerical analysis
.
Proximity problems
Computational geometry
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...
that states problems in terms of geometric objects as discrete
Discrete mathematics
Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not...
entities and hence the methods of their solution are mostly theories and algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s of combinatorial
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
character.
See List of numerical computational geometry topics for another flavor of computational geometry that deals with geometric objects as continuous entities and applies methods and algorithms of nature characteristic to numerical analysis
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
.
Construction/representation
- Boolean operations on polygonsBoolean operations on polygonsBoolean operations on polygons are a set of Boolean operations operating on one or more sets of polygons in computer graphics...
- Convex hullConvex hullIn mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
- Hyperplane arrangement
- Polygon decomposition
- Polygon triangulationPolygon triangulationIn computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding the set of triangles with pairwise non-intersecting interiors whose union is P....
- Minimal convex decomposition
- Minimal convex cover problem (NP-hardNP-hardNP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
) - Minimal rectangular decomposition
- TessellationTessellationA tessellation or tiling of the plane is a pattern of plane figures that fills the plane with no overlaps and no gaps. One may also speak of tessellations of parts of the plane or of other surfaces. Generalizations to higher dimensions are also possible. Tessellations frequently appeared in the art...
problems
- Polygon triangulation
- Shape dissection problems
- Straight skeletonStraight skeletonIn geometry, a straight skeleton is a method of representing a polygon by a topological skeleton. It is similar in some ways to the medial axis but differs in that the skeleton is composed of straight line segments, while the medial axis of a polygon may involve parabolic curves.Straight skeletons...
- Stabbing line problem
- TriangulationTriangulation (disambiguation)Triangulation refers to measurement by using triangles. Triangulation may also refer to:-Mathematics and computer science:*Subdivisions of spaces into triangles or higher dimensional simplices:...
- Delaunay triangulationDelaunay triangulationIn mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...
- Point set triangulationPoint set triangulationA triangulation of a set of points P in the plane is a triangulation of the convex hull of P, with all points from P being among the vertices of the triangulation. Triangulations are special cases of planar straight-line graphs....
- Polygon triangulationPolygon triangulationIn computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding the set of triangles with pairwise non-intersecting interiors whose union is P....
- Delaunay triangulation
- Voronoi diagramVoronoi diagramIn mathematics, a Voronoi diagram is a special kind of decomposition of a given space, e.g., a metric space, determined by distances to a specified family of objects in the space...
Extremal shapes
- Minimum bounding boxMinimum bounding boxThe minimum or smallest bounding or enclosing box for a point set in N dimensions is the box with the smallest measure within which all the points lie...
(Smallest enclosing boxSmallest enclosing boxIn computational geometry, the smallest enclosing box problem is that of finding the oriented minimum bounding box enclosing a set of points. It is a type of bounding volume. "Smallest" may refer to volume, area, perimeter, etc. of the box....
, Smallest bounding box)- 2-D case: Smallest bounding rectangle (Smallest enclosing rectangle)
- There are two common variants of this problem.
- In many areas of computer graphics, the bounding box (often abbreviated to bbox) is understood to be the smallest box delimited by sides parallel to coordinate axes which encloses the objects in question.
- In other applications, such as packaging, the problem is to find the smallest box the object (or objects) may fit in ("packaged"). Here the box may assume an arbitrary orientation with respect to the "packaged" objects.
- Smallest bounding sphere (Smallest enclosing sphere)
- 2-D case: Smallest bounding circle
- Largest empty rectangleLargest empty rectangleIn computational geometry, the largest empty rectangle problem, maximal empty rectangle problem or maximum empty rectangle problem, is the problem of finding a rectangle of maximal size to be placed among obstacles in the plane...
(Maximum empty rectangle) - Largest empty sphereLargest empty sphereIn computational geometry, the largest empty sphere problem is the problem of finding a hypersphere of largest radius in d-dimensional space whose interior does not overlap with any given obstacles.-Two dimensions:...
- 2-D case: Maximum empty circle (largest empty circle)
Interaction/search
- Collision detectionCollision detectionCollision detection typically refers to the computational problem of detecting the intersection of two or more objects. While the topic is most often associated with its use in video games and other physical simulations, it also has applications in robotics...
- Line segment intersectionLine segment intersectionIn computational geometry, the line segment intersection problem supplies a list of line segments in the plane and asks us to determine whether any two of them intersect, or cross....
- Point locationPoint locationThe point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems , motion planning, and computer aided design ....
- Point in polygonPoint in polygonIn computational geometry, the point-in-polygon problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon...
- Point in polygon
- Polygon intersection
- Range searchingRange searchingIn its most general form, the range searching problem consists of preprocessing a set S of objects, in order to determine which objects from S a query object, called a range, intersects...
- Orthogonal range searching
- Simplex range searching
- Ray castingRay castingRay casting is the use of ray-surface intersection tests to solve a variety of problems in computer graphics. It enables spatial selections of objects in ascene by providing users a virtual beam as a visual cue extending...
(not to be confused with ray tracing of computer graphics)
Proximity problemsProximity problemsProximity problems is a class of problems in computational geometry which involve estimation of distances between geometric objects.A subset of these problems stated in terms of points only are sometimes referred to as closest point problems, although the term "closest point problem" is also used...
- Closest pair of points
- Closest point problemClosest point problemClosest point problem may refer to:*Proximity problems*Nearest neighbor search...
- Diameter of a point setDiameter of a point setIn mathematics, the diameter of a point set is the maximum pairwise distance between two points in the set, or more generally, regardless of whether a maximum exists, the smallest upper bound on such distances....
- Delaunay triangulationDelaunay triangulationIn mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...
- Voronoi diagramVoronoi diagramIn mathematics, a Voronoi diagram is a special kind of decomposition of a given space, e.g., a metric space, determined by distances to a specified family of objects in the space...
Visibility
- Visibility (geometry)Visibility (geometry)Visibility is a mathematical abstraction of the real-life notion of visibility.Given a set of obstacles in the Euclidean space, two points in the space are said to be visible to each other, if the line segment that joins them does not intersect any obstacles.Computation of visibility is among the...
- Art gallery problemArt gallery problemThe 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 which together can observe the whole gallery...
(The museum problem) - Visibility graphVisibility graphIn computational geometry and robot motion planning, a visibility graph is a graph of intervisible locations, typically for a set of points and obstacles in the Euclidean plane. Each node in the graph represents a point location, and each edge represents a visible connection between them...
- Watchman route problemWatchman route problemThe Watchman Problem is an optimization problem in computational geometry where the objective is to compute the shortest route a watchman should take to guard an entire area with obstacles given only a map of the area. The challenge is to make sure the watchman peeks behind every corner and to...
- Computer graphics applications:
- Hidden surface determinationHidden surface determinationIn 3D computer graphics, hidden surface determination is the process used to determine which surfaces and parts of surfaces are not visible from a certain viewpoint...
- Hidden line removalHidden line removalHidden line removal is an extension of wireframe model rendering where lines covered by surfaces are not drawn.This is not the same as hidden face removal since this involves depth and occlusion while the other involves normals....
- Hidden surface determination
- Ray castingRay castingRay casting is the use of ray-surface intersection tests to solve a variety of problems in computer graphics. It enables spatial selections of objects in ascene by providing users a virtual beam as a visual cue extending...
(not to be confused with ray tracing of computer graphics)
Other
- Happy end problem
- Ham sandwich problem
- shape assembly problems
- shape matching problems
- Klee's measure problemKlee's measure problemIn computational geometry, Klee's measure problem is the problem of determining how efficiently the measure of a union of rectangular ranges can be computed...
- Problems on isothetic polygonIsothetic polygonAn isothetic polygon is a polygon whose alternate sides belong to two parametric families of straight lines which are pencils of lines with centers at two points...
s and isothetic polyhedra- Orthogonal convex hullOrthogonal convex hullIn Euclidean geometry, a set K\subset\R^n is defined to be orthogonally convex if, for every line L that is parallel to one of the axes of the Cartesian coordinate system, the intersection of K with L is empty, a point, or a single interval...
- Orthogonal convex hull
- Path planning
- Paths among obstacles
- Shortest path in a polygon
- Polygon containment
- Robust geometric computation addresses two main issues: fixed-precision representation of real numberReal numberIn mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s in computers and possible geometrical degeneracy (mathematics)Degeneracy (mathematics)In mathematics, a degenerate case is a limiting case in which a class of object changes its nature so as to belong to another, usually simpler, class....
of input data