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

DOI10.1016/0020-0190(87)90101-3zbMath0637.68075MaRDI QIDQ1098638

Claudio Rey, Rabab Kreidieh 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

on-line algorithm; convex hull; minimax linear fit; off-line processing; order of computational time

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

52A10: Convex sets in (2) dimensions (including convex curves)

68R99: Discrete mathematics in relation to computer science

68W99: Algorithms in computer science

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons
• Another efficient algorithm for convex hulls in two dimensions
• Maintenance of configurations in the plane
• On the multimodality of distances in convex polygons
• Uniform convergence of the empirical distribution function over convex sets
• Convex hull of a finite set of points in two dimensions
• Divide and conquer for linear expected time
• An efficient algorithm for determining the convex hull of a finite planar set
• On the identification of the convex hull of a finite set of points in the plane
• Complexity, convexity, and unimodality
• An example of cycling in a feasible point algorithm
• Algorithm 495: Solution of an Overdetermined System of Linear Equations in the Chebychev Norm [F4]
• Convex hulls of finite sets of points in two and three dimensions
• An optimal real-time algorithm for planar convex hulls