An alignment problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929589742206976 |
|---|---|
| author | McDaniel, Emma L. Mikler, Armin R. Tiwari, Chetan Patterson, Murray |
| author_facet | McDaniel, Emma L. Mikler, Armin R. Tiwari, Chetan Patterson, Murray |
| contents | This work concerns an alignment problem that has applications in many geospatial problems such as resource allocation and building reliable disease maps. Here, we introduce the problem of optimally aligning $k$ collections of $m$ spatial supports over $n$ spatial units in a $d$-dimensional Euclidean space. We show that the 1-dimensional case is solvable in time polynomial in $k$, $m$ and $n$. We then show that the 2-dimensional case is NP-hard for 2 collections of 2 supports. Finally, we devise a heuristic for aligning a set of collections in the 2-dimensional case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_08792 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An alignment problem McDaniel, Emma L. Mikler, Armin R. Tiwari, Chetan Patterson, Murray Data Structures and Algorithms Computational Complexity This work concerns an alignment problem that has applications in many geospatial problems such as resource allocation and building reliable disease maps. Here, we introduce the problem of optimally aligning $k$ collections of $m$ spatial supports over $n$ spatial units in a $d$-dimensional Euclidean space. We show that the 1-dimensional case is solvable in time polynomial in $k$, $m$ and $n$. We then show that the 2-dimensional case is NP-hard for 2 collections of 2 supports. Finally, we devise a heuristic for aligning a set of collections in the 2-dimensional case. |
| title | An alignment problem |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2411.08792 |