Geometric Algorithms for Trajectory Planning and Facility Location Optimization Problems

Date

August 2023

ORCID

Journal Title

Journal ISSN

Volume Title

Publisher

item.page.doi

Abstract

Geometry has long functioned as a bridge between abstract and real-world problems. In the field of computational geometry, we design algorithms and data structures to solve computational problems efficiently by exploiting their intrinsic geometric properties. This dissertation showcases our algorithmic contributions in utilizing computational geometry to solve a set of problems in two distinct subject areas – i) robot motion planning and ii) facility location theory. First, we describe geometric algorithms for computing feasible trajectories for an articulated two-segment robotic probe subject to specific motion constraints. We examine generalizations of the trajectory planning problem, in both two and three dimensions, with a fixed or variable end segment. Our algorithmic solutions are non-trivial and exact, as opposed to approximations and heuristics that are often employed for complex motion planning problems involving robots with restrictions and high degrees of freedom. The development of these algorithms is primarily driven by the need for precise planning in minimally invasive robotic surgeries in the medical domain. Secondly, we analyze several variations of facility location optimization problems from a geometric perspective. These problems involve finding the optimal location for a facility, either a line segment or a point, based on its distances from a set of demand points in fixed dimensions. We study variations such as discrete and center median line segments, continuous median line segment, and medoid (i.e., discrete point). To solve these problems, we create new geometric algorithms that are efficient, either exact or approximate with a relative performance guarantee. These optimization problems are considered fundamental in location science and an integral part of many industrial as well as data-science applications.

Description

Keywords

Computer Science

item.page.sponsorship

Rights

Citation