Fitting polygonal functions to a set of points in the plane
| Autor: | E. F. Schmeichel, S. L. Hakimi |
|---|---|
| Rok vydání: | 1991 |
| Předmět: |
Efficient algorithm
General Engineering Abscissa Computer Science::Computational Geometry Chebyshev filter Combinatorics Piecewise linear function symbols.namesake Monotone polygon Polygonal chain symbols General Earth and Planetary Sciences Visibility polygon Time complexity General Environmental Science Mathematics |
| Zdroj: | CVGIP: Graphical Models and Image Processing. 53:132-136 |
| ISSN: | 1049-9652 |
| Popis: | Given a set of points S = {(x1, y1), (x2, y2), …, (xN, yN)} in R2 with x1 < x2 < … < xN, we want to construct a polygonal (i.e., continuous, piecewise linear) function f with a small number of corners (i.e., nondifferentiable points) which fits S well. To measure the quality of f in this regard, we employ two criteria: 1. (i) the number of corners in the graph of f, and 2. (ii) max1≤i≤N¦yi − f(xi)¦ (the Chebyshev error of the fit). We give efficient algorithms to construct a polygonal function f that minimizes (i) (resp. (ii)) under a maximum allowable value of (ii) (resp. (i)), whether or not the comers of f are constrained to be in the set S. A key tool used in designing these algorithms is a linear time algorithm to find the visibility polygon from an edge in a monotone polygon. A variation of one of these algorithms solves the following computational geometry problem in optimal O(N) time: Given N vertical segments in the plane, no two with the same abscissa, find a monotone polygonal curve with the least number of corners which intersects all the segments. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|