Approximating points by a piecewise linear function

DOI10.1007/s00453-012-9658-yzbMath1267.68264MaRDI QIDQ2375945

Danny Z. Chen, Haitao Wang

Publication date: 25 June 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9658-y

zbMATH Keywords

outliers; computational geometry; points approximation; algorithm and data structure

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

65D18: Numerical aspects of computer graphics, image analysis, and computational geometry

Related Items

Fluctuated Fitting Under the $$\ell _1$$ -metric, An O(n log n)-Time Algorithm for the k-Center Problem in Trees, An $O(n\log n)$-Time Algorithm for the $k$-Center Problem in Trees, Efficient algorithms for the one-dimensional \(k\)-center problem, On the performance of learned data structures, Weighted \(L_{\infty}\) isotonic regression

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Representing a functional curve by curves with fewer peaks
• Fractional cascading. I: A data structuring technique
• Geometric applications of a matrix-searching algorithm
• Making data structures persistent
• Maintenance of configurations in the plane
• Finding the intersection of two convex polyhedra
• \(k\)-violation linear programming
• Efficiently approximating polygonal paths in three and higher dimensions
• Output-sensitive results on convex hulls, extreme points, and related problems
• Separation and approximation of polyhedral objects
• On geometric optimization with few violated constraints
• Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles
• A new algorithm for fitting a rectilinear x-monotone curve to a set of points in the plane
• Exact Size of Binary Space Partitionings and Improved Rectangle Tiling Algorithms
• COMPACT INTERVAL TREES: A DATA STRUCTURE FOR CONVEX HULLS
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• Fast Algorithms for Finding Nearest Common Ancestors
• Generalized Selection and Ranking: Sorted Matrices
• Fitting a Step Function to a Point Set
• Approximating Points by a Piecewise Linear Function: II. Dealing with Outliers
• A linear algorithm for determining the separation of convex polyhedra
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Linear Programming in Linear Time When the Dimension Is Fixed
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Combinatorial Optimization with Rational Objective Functions
• An on-line algorithm for fitting straight lines between data ranges
• Planar Formulae and Their Uses
• Optimal Search in Planar Subdivisions
• An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra
• Deterministic Algorithms for 2-d Convex Programming and 3-d Online Linear Programming
• Surface Approximation and Geometric Partitions
• Fitting polygonal functions to a set of points in the plane
• Approximation algorithms for MAX–MIN tiling
• Slowing down sorting networks to obtain faster sorting algorithms
• Measurement Error in a Random Walk Model with Applications to Population Dynamics
• Fitting rectilinear polgonal curves to a set of points in the plane.