On determining the on-line minimax linear fit to a discrete point set in the plane

DOI10.1016/0020-0190(87)90101-3MaRDI QIDQ1098638zbMATH OpenOpenAlexFDO

Authors Claudio Rey, Rabab K. Ward

Publication date 1987

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(87)90101-3

zbMATH Keywords

convex hullminimax linear fitoff-line processingon-line algorithmorder of computational time

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99) Algorithms in computer science (68W99)

Recommendations

• Finding the convex hull of a simple polygon
• Fitting rectilinear polgonal curves to a set of points in the plane.
• scientific article; zbMATH DE number 3945383
• ON MAINTAINING THE WIDTH AND DIAMETER OF A PLANAR POINT-SET ONLINE
• A linear-time algorithm for linear \(L_ 1\) approximation of points

Cites work

• Algorithm 495: Solution of an Overdetermined System of Linear Equations in the Chebychev Norm [F4]
• An efficient algorithm for determining the convex hull of a finite planar set
• An example of cycling in a feasible point algorithm
• An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons
• An optimal real-time algorithm for planar convex hulls
• Another efficient algorithm for convex hulls in two dimensions
• Complexity, convexity, and unimodality
• Convex hull of a finite set of points in two dimensions
• Convex hulls of finite sets of points in two and three dimensions
• Divide and conquer for linear expected time
• scientific article; zbMATH DE number 3945383 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3507890 (Why is no real title available?)
• scientific article; zbMATH DE number 3558853 (Why is no real title available?)
• scientific article; zbMATH DE number 3557226 (Why is no real title available?)
• scientific article; zbMATH DE number 3258269 (Why is no real title available?)
• Maintenance of configurations in the plane
• On the identification of the convex hull of a finite set of points in the plane
• On the multimodality of distances in convex polygons
• Uniform convergence of the empirical distribution function over convex sets

This page was built for publication: On determining the on-line minimax linear fit to a discrete point set in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1098638)