Constrained Geometric Optimization Problems
Public Deposited- Resource Type
- Creator
- Abstract
In this thesis we consider constrained geometric optimization problems. The first is a constrained version of the k-Steiner tree problem restricting the Steiner points to lie on a restricted set of curves. We solve the 1-Steiner tree problem in the Euclidean plane in optimal asymptotic time and space bounds when the Steiner point is constrained to lie on an input line. We then show how existing results can be used to generalize the result. The second problem is the smallest k-enclosing disc problem for a point set S contained in a simple polygon. In this problem we work with geodesic discs, meaning we use the geodesic distance function (i.e., the length of the shortest path). We present both a 2-approximation algorithm and an algorithm that finds the optimal radius for the smallest k-enclosing geodesic disc of a set of points inside a simple polygon. The last problem we consider is the smallest k-enclosing geodesic disc problem for a set of points in a simple polygon when the computed disc must be centred on an input chord of the polygon.
- Subject
- Language
- Publisher
- Thesis Degree Level
- Thesis Degree Name
- Thesis Degree Discipline
- Identifier
- Rights Notes
Copyright © 2023 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, research, scholarship, and teaching. Theses may only be shared by linking to Carleton University Institutional Repository and no part may be used without proper attribution to the author. No part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.
- Date Created
- 2023
Relations
- In Collection:
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
dangelo-constrainedgeometricoptimizationproblems.pdf | 2023-05-05 | Public | Download |