Randomized optimal algorithm for slope selection

DOI10.1016/0020-0190(91)90177-JzbMath0735.68087WikidataQ56607631 ScholiaQ56607631MaRDI QIDQ1182097

Ji{ří} Matoušek

Publication date: 27 June 1992

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

zbMATH Keywords

order statisticsrandomized algorithmparametric search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Algorithms for ham-sandwich cuts ⋮ \(k\)-violation linear programming ⋮ An approximation algorithm for least median of squares regression ⋮ Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications ⋮ Incomplete generalized \(L\)-statistics ⋮ Selecting distances in arrangements of hyperplanes spanned by points. ⋮ Randomized algorithm for the sum selection problem ⋮ Optimal slope selection via cuttings ⋮ Indexing moving points ⋮ On reverse shortest paths in geometric proximity graphs ⋮ Some variations on constrained minimum enclosing circle problem ⋮ THE ALIGNED K-CENTER PROBLEM ⋮ Efficient algorithms for maximum regression depth ⋮ On enclosing k points by a circle ⋮ The frechet distance revisited and extended ⋮ Diameter, width, closest line pair, and parametric searching ⋮ Optimal slope selection via expanders ⋮ Proximity problems on line segments spanned by points ⋮ Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses ⋮ Computing balanced convex partitions of lines ⋮ ON ENUMERATING AND SELECTING DISTANCES ⋮ MINKOWSKI SUM SELECTION AND FINDING ⋮ A practical approximation algorithm for the LMS line estimator ⋮ Efficient randomized algorithms for some geometric optimization problems ⋮ Counting and representing intersections among triangles in three dimensions ⋮ Optimal point movement for covering circular regions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sorting in \(c \log n\) parallel steps
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• An Optimal-Time Algorithm for Slope Selection

This page was built for publication: Randomized optimal algorithm for slope selection