Selecting distances in the plane

DOI10.1007/BF01187037MaRDI QIDQ2366232zbMATH OpenOpenAlexFDO

Authors Boris Aronov, Subhash Suri, Pankaj K. Agarwal, Micha Sharir

Publication date 29 June 1993

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01187037

zbMATH Keywords

arrangementsparametric searchrandom-sampling

Mathematics Subject Classification ID

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

Recommendations

• Selecting distances in arrangements of hyperplanes spanned by points.
• Distinct distances in the plane
• scientific article; zbMATH DE number 865995
• Distances from points to planes
• scientific article; zbMATH DE number 865979
• On distances between points on the plane
• ON ENUMERATING AND SELECTING DISTANCES
• scientific article; zbMATH DE number 866001
• scientific article; zbMATH DE number 3893918

Cites work

• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• Algorithms for Reporting and Counting Geometric Intersections
• An Efficient Parallel Biconnectivity Algorithm
• Applications of random sampling in computational geometry. II
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Arrangements of curves in the plane --- topology, combinatorics, and algorithms
• Deterministic coin tossing with applications to optimal parallel list ranking
• Finding the maximum, merging, and sorting in a parallel computation model
• Finding the median
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• On a circle placement problem
• Optimal Point Location in a Monotone Subdivision
• Parallel Prefix Computation
• Parallel Transitive Closure and Point Location in Planar Structures
• Parallelism in Comparison Problems
• Partitioning with two lines in the plane
• Slowing down sorting networks to obtain faster sorting algorithms
• Some techniques for geometric searching with implicit set representations
• Stable unmerging in linear time and constant space
• Time bounds for selection

Cited in

(17)

• Selecting distances in arrangements of hyperplanes spanned by points.
• Selection in monotone matrices and computing k th nearest neighbors
• Shortest paths in intersection graphs of unit disks
• L-infinity interdistance selection by parametric search
• Randomized vs. deterministic distance query strategies for point location on the line
• Approximate input sensitive algorithms for point pattern matching
• Algorithms for proximity problems in higher dimensions
• Intersecting disks using two congruent disks
• Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications
• One-way and round-trip center location problems
• Bottleneck matching in the plane
• On reverse shortest paths in geometric proximity graphs
• The 2-center problem in three dimensions
• Simple algorithms for partial point set pattern matching under rigid motion
• Efficient piecewise-linear function approximation using the uniform metric
• ON ENUMERATING AND SELECTING DISTANCES
• Diameter, width, closest line pair, and parametric searching

This page was built for publication: Selecting distances in the plane

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