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:
“For the most part, we are not where we are, but in a false position. Through an infirmity of our natures, we suppose a case, and put ourselves into it, and hence are in two cases at the same time, and it is doubly difficult to get out.”
—Henry David Thoreau (1817–1862)
“As long as learning is connected with earning, as long as certain jobs can only be reached through exams, so long must we take this examination system seriously. If another ladder to employment was contrived, much so-called education would disappear, and no one would be a penny the stupider.”
—E.M. (Edward Morgan)
“when it comes to my death let it be slow,
let it be pantomime, this last peep show,
so that I may squat at the edge trying on
my black necessary trousseau.”
—Anne Sexton (1928–1974)
“Shea—they call him Scholar Jack—
Went down the list of the dead.
Officers, seamen, gunners, marines,
The crews of the gig and yawl,
The bearded man and the lad in his teens,
Carpenters, coal-passers—all.”
—Joseph I. C. Clarke (1846–1925)