Name
Abstract | ||
|---|---|---|
Let $S$ be a planar $n$-point set. A triangulation for $S$ is a maximal plane straight-line graph with vertex set $S$. The Voronoi diagram for $S$ is the subdivision of the plane into cells such that each cell has the same nearest neighbors in $S$. Classically, both structures can be computed in $O(n \log n)$ time and $O(n)$ space. We study the situation when the available workspace is limited: given a parameter $s \in \{1, \dots, n\}$, an $s$-workspace algorithm has read-only access to an input array with the points from $S$ in arbitrary order, and it may use only $O(s)$ additional words of $\Theta(\log n)$ bits for reading and writing intermediate data. The output should then be written to a write-only structure. We describe a deterministic $s$-workspace algorithm for computing a triangulation of $S$ in time $O(n^2/s + n \log n \log s )$ and a randomized $s$-workspace algorithm for finding the Voronoi diagram of $S$ in expected time $O((n^2/s) \log s + n \log s \log^*s)$. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-319-21840-3_40 | WADS |
DocType | Volume | Citations |
Journal | abs/1507.03403 | 1 |
PageRank | References | Authors |
0.36 | 14 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matias Korman | 1 | 178 | 37.28 |
| Wolfgang Mulzer | 2 | 257 | 36.08 |
| André van Renssen | 3 | 104 | 19.30 |
| Marcel Roeloffzen | 4 | 1 | 0.36 |
| Paul Seiferth | 5 | 9 | 5.17 |
| Yannik Stein | 6 | 10 | 3.35 |