Theory and Algorithms Commons^™

Minimax And Maximin Fitting Of Geometric Objects To Sets Of Points, Yan B. Mayster

Electronic Theses and Dissertations

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 …