Closest pair and the post office problem for stochastic points

DOI10.1016/J.COMGEO.2012.10.010MaRDI QIDQ390124zbMATH OpenOpenAlexFDO

Authors Pegah Kamousi, Timothy M. Chan, Subhash Suri

Publication date 22 January 2014

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2012.10.010

zbMATH Keywords

computational geometrydata structuresapproximation algorithmsprobabilistic optimizationclosest pairpost office problem

Mathematics Subject Classification ID

Approximation algorithms (68W25) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• Closest pair and the post office problem for stochastic points
• scientific article; zbMATH DE number 176569
• Stochastic closest-pair problem and most-likely nearest-neighbor search in tree spaces
• Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points
• scientific article; zbMATH DE number 794264

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1113187 (Why is no real title available?)
• scientific article; zbMATH DE number 219238 (Why is no real title available?)
• scientific article; zbMATH DE number 2119699 (Why is no real title available?)
• scientific article; zbMATH DE number 3073200 (Why is no real title available?)
• (Approximate) uncertain skylines
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Approximate nearest neighbor queries revisited
• Computational geometry. Algorithms and applications.
• Counting the number of vertex covers in a trapezoid graph
• Largest and smallest convex hulls for imprecise points
• Polynomial-time approximation schemes for packing and piercing fat objects
• Preprocessing Imprecise Points and Splitting Triangulations
• Stochastic minimum spanning trees in Euclidean spaces
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Enumeration and Reliability Problems
• The complexity of counting in sparse, regular, and planar graphs
• Universality considerations in VLSI circuits

Cited in

(12)

• Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
• scientific article; zbMATH DE number 176569 (Why is no real title available?)
• Maximum box problem on stochastic points
• r-Gatherings on a star and uncertain r-gatherings on a line
• Computing Shapley values in the plane
• Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points
• Stochastic closest-pair problem and most-likely nearest-neighbor search in tree spaces
• The Most Likely Object to be Seen Through a Window
• On the arrangement of stochastic lines in \(\mathbb{R}^2\)
• scientific article; zbMATH DE number 7559220 (Why is no real title available?)
• Closest pair and the post office problem for stochastic points
• The most-likely skyline problem for stochastic points

This page was built for publication: Closest pair and the post office problem for stochastic points

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