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.)
“War and culture, those are the two poles of Europe, her heaven and hell, her glory and shame, and they cannot be separated from one another. When one comes to an end, the other will end also and one cannot end without the other. The fact that no war has broken out in Europe for fifty years is connected in some mysterious way with the fact that for fifty years no new Picasso has appeared either.”
—Milan Kundera (b. 1929)
“They will tell me I talk about things I have never experienced but only dreamed—to which I might reply: it is a lovely thing to dream such dreams! And besides, our dreams are much more our experiences than we believe—we must relearn about dreams! If I have dreamed thousands of times about flying—would you not believe that when I am awake I also possess feelings and needs giving me an edge on most people—and...”
—Friedrich Nietzsche (1844–1900)
“Every morning I woke in dread, waiting for the day nurse to go on her rounds and announce from the list of names in her hand whether or not I was for shock treatment, the new and fashionable means of quieting people and of making them realize that orders are to be obeyed and floors are to be polished without anyone protesting and faces are to be made to be fixed into smiles and weeping is a crime.”
—Janet Frame (b. 1924)