Halfedge Data Structure
The most basic way of storing scene information is normally using a shared list of vertices. Lists of faces are then added, each face containing pointers to the vertices it uses out of the shared list. While this is a straight forward way of dealing with the scene data, consider a scenario where you are interested in finding adjacent faces or vertices. Finding this sort of information will in the worst case involve searching through the entire list of vertices, the entire list of faces, or both.
The halfedge data structure allows adjacency information to be found in near constant time, making it especially useful for mesh simplification, subdivision surfaces, meshing for radiosity, and other applications where frequent access is needed to different types of adjacency information.
The Data Structure
Central to the idea of the half-edge structure is that each edge in a mesh can infact be thought of as two half-edges, and each of these half-edges can only be connected to a single face.
Note: The half-edge structure does generally not support non-manifold geometry