Doctoral Dissertations

Keywords and Phrases

Bowyer-Watson Algorithm; Delaunay triangulation; Euler-Poincare Equation; Noval Approch


“Delaunay triangulation and data structures are an essential field of study and research in computer science, for this reason, the correct choices, and an adequate design are essential for the development of algorithms for the efficient storage and/or retrieval of information. However, most structures are usually ephemeral, which means keeping all versions, in different copies, of the same data structure is expensive. The problem arises of developing data structures that are capable of maintaining different versions of themselves, minimizing the cost of memory, and keeping the performance of operations as close as possible to the original structure. Therefore, this research aims to aims to examine the feasibility concepts of Spatio-temporal structures such as persistence, to design a Delaunay triangulation algorithm so that it is possible to make queries and modifications at a certain time t, minimizing spatial and temporal complexity. Four new persistent data structures for Delaunay triangulation (Bowyer-Watson, Walk, Hybrid, and Graph) were proposed and developed. The results of using random images and vertex databases with different data (DAG and CGAL), proved that the data structure in its partial version is better than the other data structures that do not have persistence. Also, the full version data structures show an advance in the state of the technique. All the results will allow the algorithms to minimize the cost of memory”--Abstract, page iii.


Markowsky, George

Committee Member(s)

Morales, Ricardo
Taylor, Patrick
Nadendla, V. Sriram Siddhardh
Paige, Robert L.


Computer Science

Degree Name

Ph. D. in Computer Science


Missouri University of Science and Technology

Publication Date

Summer 2020


xi, 95 pages

Note about bibliography

Includes bibliographic references (pages 91-94).


© 2020 Esraa Habeeb Khaleel Al-Juhaishi, All rights reserved.

Document Type

Dissertation - Open Access

File Type




Thesis Number

T 11867