Katharina Klost, Marc van Kreveld, Daniel Perz, Günter Rote, and Josef
Tkadlec:
Minimum spanning blob-trees
In: Abstracts
of the 41st European Workshop on Computational Geometry (EuroCG
2025), Liblice, Czech Republic, April 9–11, 2025, Editors: Jan
Kratochvíl and Giuseppe Liotta, pp. 23:1–23:8. Full version: arXiv:2503.02439
→BibTeX
Abstract
We investigate blob-trees, a new way of connecting a set of points, by a
mixture of enclosing them by cycles (as in the convex hull) and connecting
them by edges (as in a spanning tree). We show that a minimum-cost blob-tree
for n points can be computed in O(n3) time.
Last update: April 14, 2025.