archives@tulane.edu / In this dissertation, we consider several topics in computational geometry motivated by applications in maps and networks in geographic scenes.
We first propose several algorithms that compute the Fr\'echet distance between curves, whose edges are relatively long. One of the popular metrics to capture the similarity between curves is the Fr\'echet distance. In particular, we give a linear-time greedy algorithm for deciding and approximating the Fr\'echet distance and a near linear-time algorithm for computing the exact Fr\'echet distance between two curves in any constant dimension.
Next, we propose efficient data structures for proximity and similarity search among curves under the Fr\'echet distance: Given a curve with $n$ vertices, for any query curve of size $m$, decide whether the Fr\'echet distance between the two curves is small or not. We give a data structure with $O(m\log^2 n)$ query time using $O(n \log n)$ space and preprocessing time. In the next stage, we explore the \emph{Approximate Near-Neighbors Queries} problem among curves: Given
a set of curves, for any query curve, the aim is to report those input curves that are `approximately' close to the query. We obtain the first result on this problem under the continuous Fr\'echet distance.
We exploit the metric studied above for simplification purposes. We specifically consider the problem of computing an alternative polygonal curve with the minimum number of links whose distance to the input curve is at most some given real value. We also propose several exact and approximation algorithms when the vertices of the output curve are selected from the input curve's vertices, its edges, any points in the ambient space.
Finally, we turn our attention to a more general type of simplification applied to trees and graphs: We are given a geometric graph and a threshold, the goal is to compute an alternative geometric graph with a minimum total number of edges and vertices such that the distance between them is at most the threshold. We detail several NP-hardness and algorithmic results depending on the type of input/output graphs, the vertex placement of the output graph, and the distance measures between them. / 1 / Majid Mirzanezhad
| Identifer | oai:union.ndltd.org:TULANE/oai:http://digitallibrary.tulane.edu/:tulane_122463 |
| Date | January 2021 |
| Contributors | Mirzanezhad, Majid (author), Wenk, Carola (Thesis advisor), School of Science & Engineering Computer Science (Degree granting institution) |
| Publisher | Tulane University |
| Source Sets | Tulane University |
| Language | English |
| Detected Language | English |
| Type | Text |
| Format | electronic, pages: 186 |
| Rights | No embargo, Copyright is in accordance with U.S. Copyright law. |
Page generated in 0.0021 seconds