A divide-and-conquer algorithm for two-point L1 shortest path queries in polygonal domains
Let $P$ be a polygonal domain of $h$ holes and $n$ vertices. We study the problem of constructing a data structure that can compute a shortest path between $s$ and $t$ in $P$ under the $L_1$ metric for any two query points $s$ and $t$. To do so, a standard approach is to first find a set of $n_s$ "g...
Saved in:
| Main Author: | |
|---|---|
| Format: | Artigo |
| Language: | Inglês |
| Published: |
Carleton University
2020-08-01
|
| Series: | Journal of Computational Geometry |
| Online Access: | https://jocg.org/index.php/jocg/article/view/3100 |
| Tags: |
No Tags, Be the first to tag this record!
|