On reporting the L₁ metric closest pair in a query rectangle

DOI10.1016/J.IPL.2013.12.006MaRDI QIDQ2446069zbMATH OpenOpenAlexFDO

Authors Ananda Swarup Das, Prosenjit Gupta, Kishore Kothapalli, Kannan Srinathan

Publication date 15 April 2014

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

Full work available at URL https://doi.org/10.1016/j.ipl.2013.12.006

zbMATH Keywords

closest paircomputational geometryManhattan metricrange queries

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Closest-pair queries in fat rectangles
• Nearest neighbor queries in metric spaces
• scientific article; zbMATH DE number 1559576
• On the Least Cost for Proximity Searching in Metric Spaces
• Approximate closest-point queries in high dimensions
• Approximate range closest-pair queries
• Combinatorial Pattern Matching
• Approximate best proximity pairs in metric space
• A simple randomized O(N N)-time closest-pair algorithm in doubling metrics
• A Randomized Algorithm for Closest-Point Queries

Cites work

• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• Optimal succinctness for range minimum queries
• Orthogonal range searching on the RAM, revisited
• Range aggregate maximal points in the plane
• Sorted range reporting
• Top-\(k\) document retrieval in optimal time and linear space

This page was built for publication: On reporting the \(L_1\) metric closest pair in a query rectangle

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