In our group, we study some of the fundamental problems in computational geometry with a focus on the data structure. Some of the main areas of research include the following. 

• Efficient data structures for geometric queries (range searching): This is a large area of research where the goal is to preprocess an input set of geometric objects, often points, and store them in a data structure so that certain queries can be answered more efficiently. Each query is often a geometric region and requests information regarding the objects lying inside that region. For instance, consider an input of points where each point represents a property with some value. In this example, a query could be a circle and we could be interested in the number of properties in the region or their total value, or the most valuable property in the region and so on. This line of research dates back to the 1970s and is motivated by various applications in databases, geographic information systems, and other fields.

• Lower bounds for geometric data structures: This complementary line of research aims to prove impossibility results that show certain space/query-time trade-offs are not possible. Such results help us reason about “optimality”: theoretical analysis of algorithms or data structures allows us to prove that they will perform with provable guarantees but if we can show that no algorithm or data structure can do substantially better, then we have shown that the solutions we have found are optimal, and thus they cannot be improved beyond constant factors; in this case, we can safely conclude that the problem has been "solved".

• Other lines of work include the following: 

  • Beyond worst-case analysis and alternative computational models. Classical theoretical analysis often focuses on worst-case scenarios within the standard unit-cost Random Access Machine (RAM) model. For some problems, these assumptions yield theoretical results that do not always reflect practical performance, creating a gap between theory and practice. By considering alternative models, this gap can be reduced. Some of the work in this area studies geometric algorithms and data structures in the Input/Output (I/O) model, the cache-oblivious model, as well as beyond worst-case measures such as adaptive analysis and instance-optimality.

Computational geometry is a core discipline of computer science that deals with geometric data and the computational tasks associated with it. As such, it has a wide range of applications:

• Modeling three-dimensional objects in computer-aided design.

• Modeling three-dimensional objects in graphical applications and solving fundamental computational tasks such as collision detection.

• It can be used in geographic information systems to model road networks and address various logistical tasks related to transportation and navigation.

• Geometric algorithms are also applied in robotics for problems such as robot motion planning, shortest path computations, and many others.