Parametric Spanning Trees: A Study in Computational Geometry

Title: Parametric Spanning Trees: A Study in Computational Geometry

Abstract: Parametric spanning trees is a concept in computational geometry that deals with finding the longest edge in a minimum weight spanning tree of a weighted, undirected connected graph with linear parametric weights. This study explores algorithms and techniques for efficiently computing parametric spanning trees and their implications in the field of computational geometry.

Main Research Question: How can we efficiently compute the longest edge in a minimum weight spanning tree of a weighted, undirected connected graph with linear parametric weights?

Methodology: The study uses techniques from computational geometry and graph theory to develop algorithms for computing parametric spanning trees. These techniques include slope selection algorithms and methods for computing all peaks in the k-level of an arrangement of lines. The research proposes an algorithm that can compute all local peaks in the k-level of an arrangement of nlines in O(nlogn) + ~O((kn)2/3) time, making it more efficient than previous methods for some restricted ranges of k.

Results: The research provides an algorithm that can compute all local peaks in the k-level of an arrangement of nlines in O(nlogn) + ~O((kn)2/3) time. It also presents a method for computing τlargest maximal peaks for τ≤k in O(nlog2n) + ~O((τn)2/3) time. The study shows that these methods are more efficient than previous methods for some ranges of k and τ.

Implications: The research on parametric spanning trees has implications in various fields of computational geometry, such as geometric algorithms, computer graphics, and robotics. The techniques developed can be used to solve other problems involving parametric curves and surfaces, and can potentially lead to more efficient algorithms for related problems. The study also contributes to the understanding of the complexity of computational problems involving parametric weights and linear parameters.

Link to Article: https://arxiv.org/abs/0103024v1 Authors: arXiv ID: 0103024v1