HOME

TheInfoList



Click Here for Items Related To - List Of Combinatorial Computational Geometry Topics
OR:
List Of Combinatorial Computational Geometry Topics on:   [Wikipedia]   [Google]   [Amazon]

List of combinatorial computational geometry topics enumerates the topics of computational geometry that states problems in terms of geometric objects as
discrete Discrete may refer to: *Discrete particle or quantum in physics, for example in quantum theory *Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit *Discrete group, a ...
entities and hence the methods of their solution are mostly theories and
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s of
combinatorial Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
character. See
List of numerical computational geometry topics List of numerical computational geometry topics enumerates the topics of computational geometry that deals with geometric objects as continuous entities and applies methods and algorithms of nature characteristic to numerical analysis. This area i ...
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 is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods th ...
.


Construction/representation

*
Boolean operations on polygons Boolean operations on polygons are a set of Boolean operations (AND, OR, NOT, XOR, ...) operating on one or more sets of polygons in computer graphics. These sets of operations are widely used in computer graphics, CAD, and in EDA (in integrated ...
* Convex hull *
Hyperplane arrangement In geometry and combinatorics, an arrangement of hyperplanes is an arrangement of a finite set ''A'' of hyperplanes in a linear, affine, or projective space ''S''. Questions about a hyperplane arrangement ''A'' generally concern geometrical, top ...
* Polygon decomposition **
Polygon triangulation In computational geometry, polygon triangulation is the partition of a polygonal area ( simple polygon) into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is . Triangulations may ...
*** Minimal convex decomposition *** Minimal convex cover problem (
NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
) *** Minimal rectangular decomposition **
Tessellation A tessellation or tiling is the covering of a surface, often a plane, using one or more geometric shapes, called ''tiles'', with no overlaps and no gaps. In mathematics, tessellation can be generalized to higher dimensions and a variety of ge ...
problems *
Shape dissection In geometry, a dissection problem is the problem of partitioning a geometric figure (such as a polytope or ball) into smaller pieces that may be rearranged into a new figure of equal content. In this context, the partitioning is called simply a ...
problems * Straight skeleton * Stabbing line problem *
Triangulation In trigonometry and geometry, triangulation is the process of determining the location of a point by forming triangles to the point from known points. Applications In surveying Specifically in surveying, triangulation involves only angle ...
**
Delaunay triangulation In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle ...
**
Point-set triangulation A triangulation of a set of points \mathcal in the Euclidean space \mathbb^d is a simplicial complex that covers the convex hull of \mathcal, and whose vertices belong to \mathcal. In the plane (when \mathcal is a set of points in \mathbb^2), tr ...
**
Polygon triangulation In computational geometry, polygon triangulation is the partition of a polygonal area ( simple polygon) into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is . Triangulations may ...
*
Voronoi diagram In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed ...


Extremal shapes

*
Minimum bounding box In geometry, the minimum or smallest bounding or enclosing box for a point set in dimensions is the box with the smallest measure (area, volume, or hypervolume in higher dimensions) within which all the points lie. When other kinds of measure ...
(
Smallest enclosing box In 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 In 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. I ...
) ** 2-D case:
Smallest bounding rectangle In 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. I ...
(
Smallest enclosing rectangle In 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. I ...
) ** There are two common variants of this problem. *** In many areas of computer graphics, the
bounding box In geometry, the minimum or smallest bounding or enclosing box for a point set in dimensions is the box with the smallest measure (area, volume, or hypervolume in higher dimensions) within which all the points lie. When other kinds of measure ...
(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 In mathematics, given a non-empty set of objects of finite extension in d-dimensional space, for example a set of points, a bounding sphere, enclosing sphere or enclosing ball for that set is an d-dimensional solid sphere containing all of these ...
(Smallest enclosing sphere) ** 2-D case: Smallest bounding circle *
Largest empty rectangle In 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. There are a number ...
(
Maximum empty rectangle In mathematical analysis, the maxima and minima (the respective plurals of maximum and minimum) of a function, known collectively as extrema (the plural of extremum), are the largest and smallest value of the function, either within a given ran ...
) *
Largest empty sphere In 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 The largest empty circl ...
** 2-D case: Maximum empty circle (
largest empty circle In 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 The largest empty circl ...
)


Interaction/search

*
Collision detection Collision detection is the computational problem of detecting the intersection (Euclidean geometry), intersection of two or more objects. Collision detection is a classic issue of computational geometry and has applications in various computing ...
*
Line segment intersection In geometry, an intersection is a point, line, or curve common to two or more objects (such as lines, curves, planes, and surfaces). The simplest case in Euclidean geometry is the line–line intersection between two distinct lines, which either ...
*
Point location The 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 (GIS), motion planning, and computer aided ...
**
Point in polygon In computational geometry, the point-in-polygon (PIP) problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon. It is a special case of point location problems and finds applications in areas that dea ...
* Polygon intersection *
Range searching In computer science, the range searching problem consists of processing a set ''S'' of objects, in order to determine which objects from ''S'' intersect with a query object, called the ''range''. For example, if ''S'' is a set of points correspond ...
**
Orthogonal range searching In computer science, the range searching problem consists of processing a set ''S'' of objects, in order to determine which objects from ''S'' intersect with a query object, called the ''range''. For example, if ''S'' is a set of points correspon ...
** Simplex range searching *
Ray casting Ray casting is the methodological basis for 3D CAD/CAM solid modeling and image rendering. It is essentially the same as ray tracing for computer graphics where virtual light rays are "cast" or "traced" on their path from the focal point of a came ...
(not to be confused with ray tracing of computer graphics) * Slab method


Proximity problems Proximity 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, ...

*
Closest pair of points The closest pair of points problem or closest pair problem is a problem of computational geometry: given n points in metric space, find a pair of points with the smallest distance between them. The closest pair problem for points in the Euclidean ...
* Closest point problem *
Diameter of a point set In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid fo ...
*
Delaunay triangulation In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle ...
*
Voronoi diagram In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed ...


Visibility

*
Visibility (geometry) In 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 n ...
*
Art gallery problem 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 the geometric version of the problem, the layout of the art gallery is represent ...
( The museum problem) *
Visibility graph In 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 rep ...
*
Watchman route problem The 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 ...
* Computer graphics applications: **
Hidden surface determination In 3D computer graphics, hidden-surface determination (also known as shown-surface determination, hidden-surface removal (HSR), occlusion culling (OC) or visible-surface determination (VSD)) is the process of identifying what surfaces and parts o ...
**
Hidden line removal In 3D computer graphics, solid objects are usually modeled by polyhedra. A face of a polyhedron is a planar polygon bounded by straight line segments, called edges. Curved surfaces are usually approximated by a polygon mesh. Computer progra ...
*
Ray casting Ray casting is the methodological basis for 3D CAD/CAM solid modeling and image rendering. It is essentially the same as ray tracing for computer graphics where virtual light rays are "cast" or "traced" on their path from the focal point of a came ...
(not to be confused with ray tracing of computer graphics)


Other

*
Happy ending problem In mathematics, the "happy ending problem" (so named by Paul Erdős because it led to the marriage of George Szekeres and Esther Klein) is the following statement: This was one of the original results that led to the development of Ramsey t ...
* Ham sandwich problem * shape assembly problems *
shape matching A shape or figure is a graphical representation of an object or its external boundary, outline, or external surface, as opposed to other properties such as color, texture, or material type. A plane shape or plane figure is constrained to lie ...
problems * Klee's measure problem *Problems on
isothetic polygon An 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 (possibly the point at infinity). The most well-known example of isothetic polygon ...
s and isothetic polyhedra **
Orthogonal convex hull In geometry, a set is defined to be orthogonally convex if, for every line that is parallel to one of standard basis vectors, the intersection of with is empty, a point, or a single segment. The term "orthogonal" refers to corresponding Cart ...
*
Path planning Motion planning, also path planning (also known as the navigation problem or the piano mover's problem) is a computational problem to find a sequence of valid configurations that moves the object from the source to destination. The term is used ...
** Paths among obstacles ** Shortest path in a polygon * Polygon containment *
Robust geometric computation In mathematics, specifically in computational geometry, geometric nonrobustness is a problem wherein branching decisions in computational geometry algorithms are based on approximate numerical computations, leading to various forms of unreliability ...
addresses two main issues: fixed-precision representation of
real number In mathematics, a real number is a number that can be used to measurement, measure a ''continuous'' one-dimensional quantity such as a distance, time, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small var ...
s in computers and possible geometrical
degeneracy (mathematics) In mathematics, a degenerate case is a limiting case of a class of objects which appears to be qualitatively different from (and usually simpler than) the rest of the class, and the term degeneracy is the condition of being a degenerate case. ...
of input data {{DEFAULTSORT:Combinatorial computational geometry topics Computational geometry Computational geometry Computational geometry Mathematics-related lists