Optimal slope selection via expanders

DOI10.1016/0020-0190(93)90234-ZzbMath0797.68155OpenAlexW2050420176WikidataQ56607630 ScholiaQ56607630MaRDI QIDQ689630

Micha Sharir, Matthew J. Katz

Publication date: 15 November 1993

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

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90234-z

zbMATH Keywords

computational geometryslope selectionexpander graphsparametric searching

Mathematics Subject Classification ID

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

Related Items (16)

Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications ⋮ Selecting distances in arrangements of hyperplanes spanned by points. ⋮ Optimal slope selection via cuttings ⋮ Continuous location of dimensional structures. ⋮ A note on searching line arrangements and applications ⋮ Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane ⋮ Efficient algorithms for maximum regression depth ⋮ One-dimensional \(k\)-center on uncertain data ⋮ Efficient algorithms for the one-dimensional \(k\)-center problem ⋮ Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses ⋮ Computing balanced convex partitions of lines ⋮ Efficient randomized algorithms for some geometric optimization problems ⋮ An O(n log n)-Time Algorithm for the k-Center Problem in Trees ⋮ Counting and representing intersections among triangles in three dimensions ⋮ An $O(n\log n)$-Time Algorithm for the $k$-Center Problem in Trees ⋮ Optimal point movement for covering circular regions

Cites Work

• Unnamed Item
• Unnamed Item
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Sorting in \(c \log n\) parallel steps
• Ramanujan graphs
• Cutting hyperplane arrangements
• Randomized optimal algorithm for slope selection
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• An Optimal-Time Algorithm for Slope Selection
• Slowing down sorting networks to obtain faster sorting algorithms
• A RANDOMIZED ALGORITHM FOR SLOPE SELECTION

This page was built for publication: Optimal slope selection via expanders