Optimization of geometric measures of sets of moving objects
| dc.contributor.author | Penha Costa, Ikaro Ruan | |
| dc.contributor.examiningcommittee | Li, Ben (Computer Science) | |
| dc.contributor.examiningcommittee | Kirkland, Steve (Mathematics) | |
| dc.contributor.examiningcommittee | Bose, Prosenjit (Carleton University) | |
| dc.contributor.supervisor | Durocher, Stephane | |
| dc.date.accessioned | 2024-07-09T21:27:36Z | |
| dc.date.available | 2024-07-09T21:27:36Z | |
| dc.date.issued | 2024-06-20 | |
| dc.date.submitted | 2024-07-08T00:31:40Z | en_US |
| dc.degree.discipline | Computer Science | |
| dc.degree.level | Master of Science (M.Sc.) | |
| dc.description.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. | |
| dc.description.note | October 2024 | |
| dc.identifier.uri | http://hdl.handle.net/1993/38314 | |
| dc.language.iso | eng | |
| dc.subject | Moving Objects | |
| dc.subject | Extent Measure | |
| dc.subject | Optimization | |
| dc.subject | Polynomial Motion | |
| dc.subject | Linear Movement | |
| dc.title | Optimization of geometric measures of sets of moving objects | |
| local.subject.manitoba | no | |
| project.funder.name | University of Manitoba |