Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2503.02715 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916642912468992 |
|---|---|
| author | Bierwirth, Mats Hütte, Julia Schnider, Patrick Speckmann, Bettina |
| author_facet | Bierwirth, Mats Hütte, Julia Schnider, Patrick Speckmann, Bettina |
| contents | We consider the $k$-center problem on the space of fixed-size point sets in the plane under the $L_{\infty}$-bottleneck distance. While this problem is motivated by persistence diagrams in topological data analysis, we illustrate it as a \emph{Restaurant Supply Problem}: given $n$ restaurant chains of $m$ stores each, we want to place supermarket chains, also of $m$ stores each, such that each restaurant chain can select one supermarket chain to supply all its stores, ensuring that each store is matched to a nearby supermarket. How many supermarket chains are required to supply all restaurants? We address this questions under the constraint that any two restaurant chains are close enough under the $L_{\infty}$-distance to be satisfied by a single supermarket chain. We provide both upper and lower bounds for this problem and investigate its computational complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_02715 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bounds for k-centers of point sets under $L_{\infty}$-bottleneck distance Bierwirth, Mats Hütte, Julia Schnider, Patrick Speckmann, Bettina Computational Geometry We consider the $k$-center problem on the space of fixed-size point sets in the plane under the $L_{\infty}$-bottleneck distance. While this problem is motivated by persistence diagrams in topological data analysis, we illustrate it as a \emph{Restaurant Supply Problem}: given $n$ restaurant chains of $m$ stores each, we want to place supermarket chains, also of $m$ stores each, such that each restaurant chain can select one supermarket chain to supply all its stores, ensuring that each store is matched to a nearby supermarket. How many supermarket chains are required to supply all restaurants? We address this questions under the constraint that any two restaurant chains are close enough under the $L_{\infty}$-distance to be satisfied by a single supermarket chain. We provide both upper and lower bounds for this problem and investigate its computational complexity. |
| title | Bounds for k-centers of point sets under $L_{\infty}$-bottleneck distance |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2503.02715 |