Back to search

University of Denver

Minimax and Maximin Fitting of Geometric Objects to Sets of Points

Abstract

dc:description.abstract

This thesis addresses several problems in the facility location sub-area of computational geometry. Let S be a set of n points in the plane. We derive algorithms for approximating S by a step function curve of size k < n, i.e., by an x-monotone orthogonal polyline ℜ with k < n horizontal segments. We use the vertical distance to measure the quality of the approximation, i.e., the maximum distance from a point in S to the horizontal segment directly above or below it. We consider two types of problems: min-ε, where the goal is to minimize the error for a given number of horizontal segments k and min-#, where the goal is to minimize the number of segments for a given allowed error ε. After O(n) preprocessing time, we solve instances of the latter in O(min{k log n, n}) time per instance. We can then solve the former problem in O(min{n2, nk log n}) time. Both algorithms require O(n) space. The second contribution is a heuristic for the min-ε problem that computes a solution within a factor of 3 of the optimal error for k segments, or with at most the same error as the k-optimal but using 2k - 1 segments. Furthermore, experiments on real data show even better results than what is guaranteed by the theoretical bounds. Both approximations run in O(n log n) time and O(n) space. Then, we present an exact algorithm for the weighted version of this problem that runs in O(n2) time and generalize the heuristic to handle weights at the expense of an additional log n factor. At this point, a randomized algorithm that runs in O(n log2 n) expected time for the unweighted version is presented. It easily generalizes to the weighted case, though at the expense of an additional log n factor. Finally, we treat the maximin problem and present an O(n3 log n) solution to the problem of finding the furthest separating line through a set of weighted points. We conclude with solutions to the "obnoxious" wedge problem: an O(n2 log n) algorithm for the general case of a wedge with its apex on the boundary of the convex hull of S and an O(n2) algorithm for the case of the apex of a wedge coming from the input set S.

Degree

thesis:*
Name thesis:degree_name
Ph.D.
Level thesis:degree_level
Dissertation

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Mayster, Yan B.
Contributors dc:contributor
  • Mario A. Lopez, Ph.D.
  • Ronald DeLyser
  • Scott Leutenegger
  • Alvaro Arias
  • Chris Gauthier-Dickey

Subjects

dc:subject × 9

Rights

dc:rights
Statement dc:rights
  • <p>Copyright is held by the author. User is responsible for all copyright compliance.</p>
  • Yan B. Mayster
Language dc:language
en

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.du.edu/etd/412

Chain of custody

source
Harvested from
University of Denver
Base URL
digitalcommons.du.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Mayster, Yan B.. Minimax and Maximin Fitting of Geometric Objects to Sets of Points. Dissertation thesis, https://digitalcommons.du.edu/etd/412