|
List Of Combinatorial Computational Geometry Topics
List of combinatorial computational geometry topics enumerates the topics of computational geometry that states problems in terms of geometric objects as discrete mathematics, discrete entities and hence the methods of their solution are mostly theories and algorithms of combinatorics, 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. Construction/representation * Boolean operations on polygons * Convex hull * Hyperplane arrangement * Polygon decomposition ** Polygon triangulation *** Minimal convex decomposition *** Minimal convex cover problem (NP-hard) *** Minimal rectangular decomposition ** Tessellation problems * Shape dissection problems * Straight skeleton * Stabbing line problem * Triangulation (geometry), Triangulation ** Delaunay triangulation ** Point-set triang ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 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. Computational complexity is central to computational geometry, with great practical significance if algorithms are used on very large datasets containing tens or hundreds of millions of points. For such sets, the difference between O(''n''2) and O(''n'' log ''n'') may be the difference between days and seconds of computation. The main impetus for the development of computational geometry as a discipline was progress in computer graphics and computer-aided design and manufacturing (CAD/CAM), but many problems in computational geometry ar ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Straight Skeleton
In 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. However, both are homotopy-equivalent to the underlying polygon.. Straight skeletons were first defined for simple polygons by ,. and generalized to planar straight-line graphs (PSLG) by . In their interpretation as projection of roof surfaces, they are already extensively discussed by . Definition The straight skeleton of a polygon is defined by a continuous shrinking process in which the edges of the polygon are moved inwards parallel to themselves at a constant speed. As the edges move in this way, the vertices where pairs of edges meet also move, at speeds that depend on the angle of the vertex. If one of these moving vertices collides with a nonadjacent edge, the polygon is split in two by the collis ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 objects. Used in computer graphics and computational geometry, a bounding sphere is a special type of bounding volume. There are several fast and simple bounding sphere construction algorithms with a high practical value in real-time computer graphics applications. In statistics and operations research, the objects are typically points, and generally the sphere of interest is the minimal bounding sphere, that is, the sphere with minimal radius among all bounding spheres. It may be proven that such a sphere is unique: If there are two of them, then the objects in question lie within their intersection. But an intersection of two non-coinciding spheres of equal radius is contained in a sphere of smaller radius. The problem of computing t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Packaging
Packaging is the science, art and technology of enclosing or protecting products for distribution, storage, sale, and use. Packaging also refers to the process of designing, evaluating, and producing packages. Packaging can be described as a coordinated system of preparing goods for transport, warehousing, logistics, sale, and end use. Packaging contains, protects, preserves, transports, informs, and sells. In many countries it is fully integrated into government, business, institutional, industrial, and personal use. Package labeling (American English) or labelling (British English) is any written, electronic, or graphic communication on the package or on a separate but associated label. History of packaging Ancient era The first packages used the natural materials available at the time: baskets of reeds, wineskins ( bota bags), wooden boxes, pottery vases, ceramic amphorae, wooden barrels, woven bags, etc. Processed materials were used to form packages as they were ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 are used, the minimum box is usually called accordingly, e.g., "minimum-perimeter bounding box". The minimum bounding box of a point set is the same as the minimum bounding box of its convex hull, a fact which may be used heuristically to speed up computation. The terms "box" and "hyperrectangle" come from their usage in the Cartesian coordinate system, where they are indeed visualized as a rectangle (two-dimensional case), rectangular parallelepiped (three-dimensional case), etc. In the two-dimensional case it is called the minimum bounding rectangle. Axis-aligned minimum bounding box The axis-aligned minimum bounding box (or AABB) for a given point set is its minimum bounding box subject to the constraint that the edges of the bo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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. It is sufficient to find the smallest enclosing box for the convex hull of the objects in question. It is straightforward to find the smallest enclosing box that has sides parallel to the coordinate axes; the difficult part of the problem is to determine the orientation of the box. Two dimensions For the convex polygon, a linear time algorithm for the minimum-area enclosing rectangle is known. It is based on the observation that a side of a minimum-area enclosing box must be collinear with a side of the convex polygon. It is possible to enumerate boxes of this kind in linear time with the approach called rotating calipers by Godfried Toussaint in 1983.. The same approach is applicable for finding the minimum-perimeter enclosing rectangl ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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. It is sufficient to find the smallest enclosing box for the convex hull of the objects in question. It is straightforward to find the smallest enclosing box that has sides parallel to the coordinate axes; the difficult part of the problem is to determine the orientation of the box. Two dimensions For the convex polygon, a linear time algorithm for the minimum-area enclosing rectangle is known. It is based on the observation that a side of a minimum-area enclosing box must be collinear with a side of the convex polygon. It is possible to enumerate boxes of this kind in linear time with the approach called rotating calipers by Godfried Toussaint in 1983.. The same approach is applicable for finding the minimum-perimeter enclosing rectangl ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 are used, the minimum box is usually called accordingly, e.g., "minimum-perimeter bounding box". The minimum bounding box of a point set is the same as the minimum bounding box of its convex hull, a fact which may be used heuristically to speed up computation. The terms "box" and "hyperrectangle" come from their usage in the Cartesian coordinate system, where they are indeed visualized as a rectangle (two-dimensional case), rectangular parallelepiped (three-dimensional case), etc. In the two-dimensional case it is called the minimum bounding rectangle. Axis-aligned minimum bounding box The axis-aligned minimum bounding box (or AABB) for a given point set is its minimum bounding box subject to the constraint that the edges of the box ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 there is a corresponding region, called a Voronoi cell, consisting of all points of the plane closer to that seed than to any other. The Voronoi diagram of a set of points is dual to that set's Delaunay triangulation. The Voronoi diagram is named after mathematician Georgy Voronoy, and is also called a Voronoi tessellation, a Voronoi decomposition, a Voronoi partition, or a Dirichlet tessellation (after Peter Gustav Lejeune Dirichlet). Voronoi cells are also known as Thiessen polygons. Voronoi diagrams have practical and theoretical applications in many fields, mainly in science and technology, but also in visual art. The simplest case In the simplest case, shown in the first picture, we are given a finite set of points in the Euclidean ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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), triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of \mathcal are vertices of its triangulations. In this case, a triangulation of a set of points \mathcal in the plane can alternatively be defined as a maximal set of non-crossing edges between points of \mathcal. In the plane, triangulations are special cases of planar straight-line graphs. A particularly interesting kind of triangulations are the Delaunay triangulations. They are the geometric duals of Voronoi diagrams. The Delaunay triangulation of a set of points \mathcal in the plane contains the Gabriel graph, the nearest neighbor graph and the minimal spanning tree of \mathcal. Triangulations have a number o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
