Closest pair and the post office problem for stochastic points

DOI10.1016/j.comgeo.2012.10.010zbMath1315.65018OpenAlexW2089984367MaRDI QIDQ390124

Timothy M. Chan, Subhash Suri, Pegah Kamousi

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

data structurescomputational geometryapproximation algorithmsprobabilistic optimizationclosest pairpost office problem

Mathematics Subject Classification ID

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

Related Items (11)

On the arrangement of stochastic lines in \(\mathbb{R}^2\) ⋮ Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points ⋮ Convex hulls under uncertainty ⋮ r-Gatherings on a star and uncertain r-gatherings on a line ⋮ The Most Likely Object to be Seen Through a Window ⋮ Unnamed Item ⋮ Maximum box problem on stochastic points ⋮ The most-likely skyline problem for stochastic points ⋮ Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle ⋮ On the expected diameter, width, and complexity of a stochastic convex hull ⋮ Computing Shapley values in the plane

Cites Work

• (Approximate) uncertain skylines
• Largest and smallest convex hulls for imprecise points
• Counting the number of vertex covers in a trapezoid graph
• Approximate nearest neighbor queries revisited
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• The Complexity of Enumeration and Reliability Problems
• Universality considerations in VLSI circuits
• Polynomial-time approximation schemes for packing and piercing fat objects
• Preprocessing Imprecise Points and Splitting Triangulations
• Stochastic minimum spanning trees in euclidean spaces
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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