Improved algorithms for distance selection and related problems

DOI10.1007/S00453-025-01305-ZMaRDI QIDQ6979990zbMATH OpenFDO

Authors Haitao Wang, Yiming Zhao

Publication date 23 May 2025

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00453-025-01305-Z

zbMATH Keywords

distance selectionFréchet distancegeometric optimizationrange searching

Mathematics Subject Classification ID

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

Cites work

• An Expander-Based Approach to Geometric Optimization
• Computing the discrete Fréchet distance in subquadratic time
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• Computing the Fréchet distance with shortcuts is NP-hard
• Cutting hyperplanes for divide-and-conquer
• Hopcroft's problem, log-star shaving, 2D fractional cascading, and decision trees
• scientific article; zbMATH DE number 7051233 (Why is no real title available?)
• scientific article; zbMATH DE number 6861957 (Why is no real title available?)
• Jaywalking your dog: computing the Fréchet distance with shortcuts
• Near-optimal algorithms for shortest paths in weighted unit-disk graphs
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• ON ENUMERATING AND SELECTING DISTANCES
• Randomized optimal algorithm for slope selection
• Reverse shortest path problem for unit-disk graphs
• Reverse shortest path problem in weighted unit-disk graphs
• Selecting distances in the plane
• The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection
• Unit-disk range searching and applications

This page was built for publication: Improved algorithms for distance selection and related problems

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