Utah State University researchers have published a series of findings in computational geometry and graph theory, introducing new algorithms that achieve optimal time and space complexity for complex mathematical problems. The research, which includes work by Haitao Wang, addresses long-standing challenges in graph diameters, shortest path mapping, and unit-disk range searching.
Optimizing Unicycle Graph Diameters
In a 2021 conference paper, researchers Haitao Wang and Yiming Wang presented a new O(n) time algorithm for computing the diameter of a unicycle graph, which is defined as a graph containing a unique cycle. This new method improves upon the previous best solution of O(n log n) time established by Oh and Ahn in 2016.
The researchers also utilized this algorithm as a subroutine to solve the problem of adding a shortcut to a tree in a way that minimizes the diameter of the resulting unicycle graph. Their algorithm for this task operates in O(n^2 log n) time and O(n) space. This represents a significant improvement over previous methods, such as the O(n^2 log^3 n) time and O(n) space solution by Oh and Ahn in 2016, or the O(n^2) time and O(n^2) space solution by Bilò in 2018.
Advancements in Range Searching
Research published in 2022 focused on unit-disk range searching, which involves computing the number of points from a set P in a query unit disk where all disks share the same radius. Haitao Wang demonstrated that techniques used for simplex range searching could be adapted for this problem.
The research provided several data structure options for this problem. One method builds a data structure requiring O(n) space that can answer each query in O(sqrt(n)) time. Alternatively, a data structure with O(n^2/log^2 n) space can achieve an O(log n) query time. The study also introduced an optimal O(n^{4/3}) time algorithm for the batched unit-disk range counting problem, matching the Ω(n^{4/3})-time lower bound.
Further applications of these techniques include solving the problem of counting intersecting pairs of circles for a set of n unit circles in the plane. The researchers achieved an O(n^{4/3}) time optimal algorithm. For cases with a small number of intersecting pairs, denoted as χ, the algorithm can be improved to O(n^{2/3}χ^{1/3}+n^{1+δ}) time for any δ > 0.
The research also addressed the distance selection problem, which seeks to find the k-th smallest distance among all pairwise distances of a set P of n points. While previous deterministic algorithms ran in O(n^{4/3}log^2 n) time, the new randomized algorithm runs in O(n log n + n^{2/3}k^{1/3}log n) expected time. Additionally, for the discrete 2-center problem—finding two smallest congruent disks whose union covers a set P—the researchers provided both a deterministic O(n^{4/3}log^{10/3} n⋅ (log log n)^{O(1)}) time algorithm and a randomized O(n^{4/3}log^3 n⋅ (log log n)^{1/3}) expected time algorithm.
Shortest Paths and Obstacles
In a 2021 study presented at the ACM-SIAM Symposium on Discrete Algorithms, Haitao Wang addressed the classical problem of finding an obstacle-avoiding Euclidean shortest path between two points among a set of pairwise disjoint polygonal obstacles. This research settled a question that had remained open for over two decades: whether the space required for the algorithm could be reduced to O(n).
