Computer Science - Geometric van Emde Boas trees for efficient point location and range searching
Supervisor: Dr. Konstantinos Tsakalidis
Supervisor bio:
Dr. Konstantinos Tsakalidis is a Lecturer at the School of Computer Science and Informatics of the University of Liverpool, and a Lead Researcher at the Archimedes AI Research Unit of the ATHEN? Research Center. He is an expert in geometric algorithms and data structures, big data computing and interdisciplinary applications of computational geometry to electromicroscopic and medical image analysis and to the foundations of deep learning.
Email: k.tsakalidis@liverpool.ac.uk
School: School of Computer Science and Informatics
Department: Computer Science
Module code: COMP298
Suitable for students of Computer Science, algorithms, programming, mathematics, geometry.
Desirable experience/requirements:
The student should be able to code in C++ [a,b] and to be familiar with algorithmic analysis [c].
[a] “C++ Programming Language”, 4th Edition (ISBN-13 978-0321958327), by Bjarne Stroustrup.
[b] “Sams Teach Yourself C++ In 21 Days”, 5th Edition (ISBN-13 978-0672327117), by Jesse Liberty, Bradley L. Jones.
[c] “Introduction to Algorithms”, 4th Edition (ISBN-13 978-0262046305) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
Places available: 2
Start date: Session 1 (15th June 2026),Session 2 (6th July 2026)
Project length: 4 or 8 weeks
Virtual option: Yes
Hybrid option: Yes
Project description:
The classic dynamic data structure ‘van Emde Boas trees’ [1,2] supports updates of n stored keys and searching for a key in one dimension in very fast O(loglogn) time. Two-dimensional geometric variants of the van Emde Boas trees contribute to dynamic orthogonal point location, i.e., to search for the region of a planar orthogonal subdivision containing a given planar point [3], and dynamic orthogonal range searching, i.e., to search for the points on the plane contained in a given planar rectangle [4]. The objective of the project is to implement the two-dimensional variants of van Emde Boas trees using CGAL [5], the computational geometry algorithms library for C++, and to evaluate them in practice, aiming to establish geometric software benchmarks for point location and range searching.
[1] P. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Inform. Process. Lett. 6(3) (1977), 80–82. https://www.sciencedirect.com/science/article/abs/pii/002001907790031X
[2] P. van Emde Boas, R. Kaas, E. Zijlstra. Design and implementation of an efficient priority queue. Mathematical systems theory. (1976) Dec;10(1):99-127. https://link.springer.com/article/10.1007/BF01683268
[3] T. M. Chan, K. Tsakalidis. Dynamic planar orthogonal point location in sublogarithmic time. In 34th International Symposium on Computational Geometry (SoCG 2018) 2018 (pp. 25-1). Schloss Dagstuhl–Leibniz-Zentrum für Informatik. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.25
[4] T. M. Chan, K. Tsakalidis. Dynamic orthogonal range searching on the RAM, revisited. Journal of Computational Geometry. (2018) 9(2):45-66. https://jocg.org/index.php/jocg/article/view/3065
[5] The Computational Geometry Algorithms Library https://www.cgal.org/
Additional requirements: N/A