Research

My research spans a wide range of problems and applications in Computational Geometry, Geographic Information Systems (GIS), and Transportation. Some notable projects are summarized below:  

Curve Similarity under the Fréchet Distance

The Fréchet distance is considered an appropriate metric to capture the similarity between the curves. It is, intuitively, the minimum length of the leash connecting a man and dog walking along two curves each without going backward.  It roughly takes quadratic time to compute the Fréchet distance between two piecewise linear curves.

I have a nice proof in my IJCGA paper demonstrating that the runtime can be significantly improved when the two curves have relatively long edges. This induces nice structural properties in the product space of point-to-point distance between curves, allowing a greedy procedure to work prevailing the classic dynamic program. Curve similarity has applications in molecular biology, shape analysis, GIS, image processing, and others. 

Geometric Simplification

Given a curve and an error ∂, we are asked to find an alternative curve with the minimum number of vertices whose distance to the original curve is at most ∂. In my ESA paper, we systematically investigated the problem and obtained several NP-hardness and algorithmic results depending on the distance measure (Fréchet and Hausdorff) used for capturing the error, the placement of the output curve, etc.

In the case we deal with a graph, our goal is to find another graph with a minimum number of vertices and/or edges so that the distance between the two graphs is at most ∂. In this preprint we proposed several NP-hardness and algorithmic results depending on the type of input/output graphs and the type of  distance measures between them. Graph simplification can be used in map-matching, mesh-simplification, and map construction.

Proximity Search Data Structures for Curves 

Similarity search is harnessed in pattern recognition, computer vision, anomaly detection, DNA sequencing, databases, GIS, etc. In the IJCGA paper, I looked into the Distance Oracle Queries in which a single curve is given and the aim is to preprocess the curve into a data structure so that it for any query curve it quickly decides whether the Fréchet distance between between the two curves is small or not.

In the Nearest-Neighbor variants, the task is to preprocess a "bunch" of curves into a data structure to quickly find the closest curve in the database for any query curve. In my paper I show how to build a data structure that handles the nearest-neighbor queries under (continuous) Frechet distance among curves in a linear query time within the approximation factor of (1+ε). 

Energy Efficient Sampling For Last-Mile Delivery Systems

Due to the emergence of e-commerce, urban freight data analysis is crucial for informed decision-making, resource allocation, and optimizing routes, especially when managing energy utilization in electric devices. The burgeoning emphasis on mitigating greenhouse gas emissions in the transportation sector has spurred companies' heightened interest in adopting Electric Vehicles (EVs) owing to their environmental benefits.

In our patent, we develop algorithmic and optimization techniques, enabling precise energy management and predicting energy consumption per trip at the road segment level to detect energy-draining spots in the city. The prospective methods will hold promise for diverse delivery systems and other micro-mobility services reliant on geolocation data, such as automated guided vehicles (AGVs) operating in industrial settings and electric vehicles (EVs) confronting battery life limitations relative to travel range. By accurately forecasting energy demands, we pave the way for more efficient and sustainable operations across a spectrum of mobility applications.