AN EFFICIENT DATA STRUCTURE FOR THE ADVANCING FRONT TRIANGULAR MESH GENERATION TECHNIQUE

A new approach is presented to optimize the search, deletion and inser tion operations in the advancing-front triangular grid generation tech nique. This approach is based on the heap, hash table and linked list data structures. The basic idea is to use different data structures fo r different operations. When the front is updated after forming an ele ment, a hash table with doubly linked lists is used to speed up search ing, deleting, and inserting operations. On the other hand, a heap is used to select the shortest side for constructing each new element. Th erefore, there is a need for two copies of the generation front: one i s stored in the hash table with doubly linked lists, and the other one in the heap. For each element generated, this approach is able to sea rch for a side to be removed from the front in a constant time on aver age, and delete and insert a side from and into the front in O(logN) t ime on average, where N is the number of sides in the front. The techn ique is also capable of searching and selecting the shortest side from the front for creating a new element in O(1) time. Several examples a re included to demonstrate the performance of the approach.