Research

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.

• Progressive Simplification of Maps in ArcGIS:  I designed an ArcPy toolbox to simplify a network representing the river of the Austin, TX area. The interesting feature of this toolbox is that given a 'zoom threshold', it gives you a simplification based on the resolution you desire faster than the existing methods. I used a shapefile and applied a heuristic algorithm which was a combination of the Douglas-Peucker (POINT-REMOVE tool) and Wang-Muller algorithms (BEND-SIMPLIFY tool). My invented tool produced a nice map in a faster execution time. Besides, the GIS course itself taught us how to use different features of the network analysis tool to solve the problems of interest on our end.  Here's the GitHub link to the toolbox I created using ArcPy: https://github.com/arminia/Simplification