Name
Abstract | ||
|---|---|---|
We present a generalization of a combinatorial result from Aggarwal, Guibas, Saxe and Shor [1] on selecting a fraction of leaves, with pairwise disjoint neighborhoods, in a tree embedded in the plane. This result has been used by linear-time algorithms to compute certain tree-like Voronoi diagrams, such as the Voronoi diagram of points in convex position. Our generalization allows that only a fraction of the tree leaves is considered: Given is a plane tree T of n leaves, m of which have been marked. Each marked leaf is associated with a neighborhood (a subtree of T) and any topologically consecutive marked leaves have disjoint neighborhoods. We show how to select in linear time a constant fraction of the marked leaves that have pairwise disjoint neighborhoods. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/978-3-030-11509-8_16 | ALGORITHMS AND DISCRETE APPLIED MATHEMATICS, CALDAM 2019 |
Keywords | DocType | Volume |
Tree, Linear-time algorithm, Neighborhood, Voronoi diagram | Conference | 11394 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kolja Junginger | 1 | 0 | 0.68 |
| Ioannis Mantas | 2 | 0 | 2.03 |
| Evanthia Papadopoulou | 3 | 110 | 18.37 |