Minimum Path Star Topology Algorithms for Weighted Regions and Obstacles
Journal Articles
Overview
Research
View All
Overview
abstract
Shortest path algorithms have played a key role in the past century, paving
the way for modern day GPS systems to find optimal routes along static systems
in fractions of a second. One application of these algorithms includes
optimizing the total distance of power lines (specifically in star topological
configurations). Due to the relevancy of discovering well-connected electrical
systems in certain areas, finding a minimum path that is able to account for
geological features would have far-reaching consequences in lowering the cost
of electric power transmission. We initialize our research by proving the
convex hull as an effective bounding mechanism for star topological minimum
path algorithms. Building off this bounding, we propose novel algorithms to
manage certain cases that lack existing methods (weighted regions and
obstacles) by discretizing Euclidean space into squares and combining
pre-existing algorithms that calculate local minimums that we believe have a
possibility of being the absolute minimum. We further designate ways to
evaluate iterations necessary to reach some level of accuracy. Both of these
novel algorithms fulfill certain niches that past literature does not cover.