Half-edge_data_structure
The doubly connected edge list (DCEL), also known as half-edge data structure, 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[1] for representations of 3D convex polyhedra. Simplified versions of the data structure, as described here, only consider connected graphs, but the DCEL structure may be extended to handle disconnected graphs as well by introducing dummy edges between disconnected components.[2]