Simple Construction of Greedy Trees and Greedy Permutations
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916506038697984 |
|---|---|
| author | Chubet, Oliver Sheehy, Don Sheth, Siddharth |
| author_facet | Chubet, Oliver Sheehy, Don Sheth, Siddharth |
| contents | \begin{abstract}
Greedy permutations, also known as Gonzalez Orderings or Farthest Point Traversals are a standard way to approximate $k$-center clustering and have many applications in sampling and approximating metric spaces.
A greedy tree is an added structure on a greedy permutation that tracks the (approximate) nearest predecessor.
Greedy trees have applications in proximity search as well as in topological data analysis.
For metrics of doubling dimension $d$, a $2^{O(d)}n\log n$ time algorithm is known, but it is randomized and also, quite complicated.
Its construction involves a series of intermediate structures and $O(n \log n)$ space.
In this paper, we show how to construct greedy permutations and greedy trees using a simple variation of an algorithm of Clarkson that was shown to run in $2^{O(d)}n\log Δ$ time, where the spread $\spread$ is the ratio of largest to smallest pairwise distances.
The improvement comes from the observation that the greedy tree can be constructed more easily than the greedy permutation.
This leads to a linear time algorithm for merging two approximate greedy trees and thus, an $2^{O(d)}n \log n$ time algorithm for computing the tree.
Then, we show how to extract a $(1+\frac{1}{n})$-approximate greedy permutation from the approximate greedy tree in the same asymptotic running time. \end{abstract} |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_02554 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Simple Construction of Greedy Trees and Greedy Permutations Chubet, Oliver Sheehy, Don Sheth, Siddharth Computational Geometry Data Structures and Algorithms \begin{abstract} Greedy permutations, also known as Gonzalez Orderings or Farthest Point Traversals are a standard way to approximate $k$-center clustering and have many applications in sampling and approximating metric spaces. A greedy tree is an added structure on a greedy permutation that tracks the (approximate) nearest predecessor. Greedy trees have applications in proximity search as well as in topological data analysis. For metrics of doubling dimension $d$, a $2^{O(d)}n\log n$ time algorithm is known, but it is randomized and also, quite complicated. Its construction involves a series of intermediate structures and $O(n \log n)$ space. In this paper, we show how to construct greedy permutations and greedy trees using a simple variation of an algorithm of Clarkson that was shown to run in $2^{O(d)}n\log Δ$ time, where the spread $\spread$ is the ratio of largest to smallest pairwise distances. The improvement comes from the observation that the greedy tree can be constructed more easily than the greedy permutation. This leads to a linear time algorithm for merging two approximate greedy trees and thus, an $2^{O(d)}n \log n$ time algorithm for computing the tree. Then, we show how to extract a $(1+\frac{1}{n})$-approximate greedy permutation from the approximate greedy tree in the same asymptotic running time. \end{abstract} |
| title | Simple Construction of Greedy Trees and Greedy Permutations |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.02554 |