The location structure is structured in several levels. The lowest level just consists in the triangulation, then each level contain the triangulation of a small sample of the levels below. Point location is done by marching in a triangulation to determine the nearest neighbor of the query at that level, then the march restart from that neighbor at the level below. Using a small sample (3 \%) allows a small memory occupation; the march and the use of the nearest neighbor to change permit to locate quickly the query.
The deletion is implemented by duality with the convex hull in 3D using a partial shelling.
|Last modified: Tue Jan 17 11:08:28 CET 2006||Olivier Devillers||Software|