The doubly connected edge list (DCEL) 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 (vertices, edges, faces). 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.
This data structure was originally suggested by Muller and Preparata for representations of 3D convex polyhedra.
Later a somewhat different data structuring was suggested, but the name "DCEL" was retained.
For simplicity, only connected graphs are considered, however the DCEL structure may be extended to handle disconnected graphs as well.
Read more about Doubly Connected Edge List: Data Structure
Famous quotes containing the words doubly, connected, edge and/or list:
“A man calumniated is doubly injured—first by him who utters the calumny, and then by him who believes it.”
—Herodotus (c. 484–425 B.C.)
“Nothing fortuitous happens in a child’s world. There are no accidents. Everything is connected with everything else and everything can be explained by everything else.... For a young child everything that happens is a necessity.”
—John Berger (b. 1926)
“A whisper ran along the edge of the dawn.”
—Zora Neale Hurston (1891–1960)
“Love’s boat has been shattered against the life of everyday. You and I are quits, and it’s useless to draw up a list of mutual hurts, sorrows, and pains.”
—Vladimir Mayakovsky (1893–1930)