Optimization of geometric measures of sets of moving objects
Loading...
Date
2024-06-20
Authors
Penha Costa, Ikaro Ruan
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Given a set S of objects, each moving with linear motion in R^d, consider the diameter D(S, t) of S at time t. In this thesis we explore optimization of extent and proximity measures of S. For instance, one possibility is to identify minimum
diameter D(S, t) of S over the domain of time t. D(S, t) is an example of a measure of extent of S. On the basis of this model, other geometric measures could also be explored to be optimized for sets of objects in motion. Let n be the cardinality of S and let M(S, t) be a geometric measure of extent or proximity at time t. Given an integer k, select a subset Q ⊂ S such that |Q| = k and Q has extreme measure M(Q, t) over all possible subsets Q of cardinality k. The present thesis focuses on minimizing and maximizing M(Q, t), in one and two dimensions (d = 1 or d = 2), for which the measure corresponds to set diameter, set width, minimum axis-aligned bounding box, and minimum enclosing disk. For each measure, exact polynomial-time algorithms are proposed for selecting an optimal subset of S and finding the time t of which the subset optimizes the measure.
Description
Keywords
Moving Objects, Extent Measure, Optimization, Polynomial Motion, Linear Movement