On selecting a fraction of leaves with disjoint neighborhoods in a plane tree
| Autor: | Junginger, Kolja, Mantas, Ioannis, Papadopoulou, Evanthia |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Zdroj: | Discrete Applied Mathematics, 319:141-148, 2022 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.dam.2021.02.002 |
| Popis: | We present a generalization of a combinatorial result by Aggarwal, Guibas, Saxe and Shor [Discrete & Computational Geometry, 1989] on a linear-time algorithm that selects a constant fraction of leaves, with pairwise disjoint neighborhoods, from a binary tree embedded in the plane. This result of Aggarwal et al. is essential to the linear-time framework, which they also introduced, that computes certain Voronoi diagrams of points with a tree structure in linear time. An example is the diagram computed while updating the Voronoi diagram of points after deletion of one site. Our generalization allows that only a fraction of the tree leaves is considered, and it is motivated by linear-time Voronoi constructions for non-point sites. We are given a plane tree $T$ of $n$ leaves, $m$ of which have been marked, and each marked leaf is associated with a neighborhood (a subtree of $T$) such that any two topologically consecutive marked leaves have disjoint neighborhoods. We show how to select in linear time a constant fraction of the marked leaves having pairwise disjoint neighborhoods. Comment: 17 pages, 9 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|