Optimal slope selection via cuttings

DOI10.1016/S0925-7721(97)00025-4zbMath0898.68033WikidataQ56607625 ScholiaQ56607625MaRDI QIDQ1388130

Hervé Brönnimann, Bernard Chazelle

Publication date: 11 October 1998

Published in: Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

slope selectioncuttings

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)

Related Items (15)

Selecting distances in arrangements of hyperplanes spanned by points. ⋮ 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 ⋮ Proximity problems on line segments spanned by points ⋮ Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses ⋮ Efficient algorithms for the sum selection problem and \(k\) maximum sums problem ⋮ Computing balanced convex partitions of lines ⋮ Efficient randomized algorithms for some geometric optimization problems ⋮ Extremal problems on triangle areas in two and three dimensions ⋮ 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

Cites Work

• Unnamed Item
• Diameter, width, closest line pair, and parametric searching
• Optimal slope selection via expanders
• Sorting in \(c \log n\) parallel steps
• Randomized optimal algorithm for slope selection
• Cutting hyperplanes for divide-and-conquer
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• An Optimal-Time Algorithm for Slope Selection
• Sorting X + Y
• A RANDOMIZED ALGORITHM FOR SLOPE SELECTION

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