Minimum Monotone Spanning Trees
Abstract Given a finite set S of points in the plane and a finite set $$\mathcal {D}$$ D of directions, a geometric spanning tree T of S is $$\mathcal {D}$$ D -monotone if every path in T is monotone with respect to some direction in $$\mathcal {D}$$ D . We study the problem of computing, for a given point set S and a given set $$\mathcal {D}$$ D of directions, a minimum-length $$\mathcal{D}$$ D -monotone spanning tree of S . We present a quadratic-time algorithm for two directions. More generally, we show that the problem belongs to the complexity class XP when parameterized by the number of directions. We further study, for a given positive integer k and point set S , the problem of finding a minimum-length $$\mathcal {D}$$ D -monotone spanning tree of S over all possible sets $$\mathcal {D}$$ D of k directions. We prove that this problem, too, is in XP when parameterized by k , and present two algorithms that run in $$O(n^2 \log n)$$ O ( n 2 log n ) and $$O(n^6)$$ O ( n 6 ) time for $$k=1$$ k = 1 and $$k=2$$ k = 2 , respectively, where n is the number of points in S . Finally, in contrast to the classical Euclidean minimum spanning tree of a set of points, whose vertex degree is bounded by six, we show that for every even integer k , there exists a point set $$S_k$$ S k and a set $$\mathcal {D}_k$$ D k of k directions such that any minimum-length $$\mathcal {D}_k$$ D k -monotone spanning tree of $$S_k$$
Authors
- Antonios Symvonis (ORCID: https://orcid.org/0000-0002-0280-741X)
- Alexander Wolff (ORCID: https://orcid.org/0000-0001-5872-718X)
- Walter Didimo (ORCID: https://orcid.org/0000-0002-4379-6059)
- Emilio Di Giacomo (ORCID: https://orcid.org/0000-0002-9794-1928)
- Lena Schlipf (ORCID: https://orcid.org/0000-0001-7043-1867)
- Eleni Katsanou (ORCID: https://orcid.org/0000-0002-1001-1411)
Publication Details
- Journal
- Algorithmica
- Published
- 2026-11-16
- DOI
- https://doi.org/10.1007/s00453-026-01409-0
- Primary Topic
- Computational Geometry and Mesh Generation
- Type
- article
- Field-Weighted Citation Impact
- 0.00