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

A new approach is presented to optimize the search, deletion and insertion operations in the advancing-front triangular grid generation technique. This approach is based on the heap, hash table and linked list data structures. The basic idea is to use different data structures for different operations. When the front is updated after forming an element, a hash table with doubly linked lists is used to speed up searching, deleting, and inserting operations. On the other hand, a heap is used to select the shortest side for constructing each new element. Therefore, there is a need for two copies of the generation front: one is 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 search for a side to be removed from the front in a constant time on average, and delete and insert a side from and into the front in O(logN) time on average, where N is the number of sides in the front. The technique is also capable of searching and selecting the shortest side from the front for creating a new element in O(1) time. Several examples are included to demonstrate the performance of the approach.