From proximity to utility: a Voronoi partition of Pareto optima
From MaRDI portal
Publication:331376
DOI10.1007/S00454-016-9808-0zbMATH Open1352.52032arXiv1404.3403OpenAlexW1488581414MaRDI QIDQ331376FDOQ331376
Authors: Hsien-Chih Chang, Sariel Har-Peled, Benjamin Raichel 
Publication date: 27 October 2016
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Abstract: We present an extension of Voronoi diagrams where when considering which site a client is going to use, in addition to the site distances, other site attributes are also considered (for example, prices or weights). A cell in this diagram is then the locus of all clients that consider the same set of sites to be relevant. In particular, the precise site a client might use from this candidate set depends on parameters that might change between usages, and the candidate set lists all of the relevant sites. The resulting diagram is significantly more expressive than Voronoi diagrams, but naturally has the drawback that its complexity, even in the plane, might be quite high. Nevertheless, we show that if the attributes of the sites are drawn from the same distribution (note that the locations are fixed), then the expected complexity of the candidate diagram is near linear. To this end, we derive several new technical results, which are of independent interest. In particular, we provide a high-probability, asymptotically optimal bound on the number of Pareto optima points in a point set uniformly sampled from the -dimensional hypercube. To do so we revisit the classical backward analysis technique, both simplifying and improving relevant results in order to achieve the high-probability bounds.
Full work available at URL: https://arxiv.org/abs/1404.3403
Recommendations
Voronoi diagramsbackward analysiscandidate diagramClarkson-Shor techniqueexpected complexityPareto optima
Cites Work
- \(\epsilon\)-nets and simplex range queries
- Applications of random sampling in computational geometry. II
- Voronoi diagrams and Delaunay triangulations
- A SIMPLE ON-LINE RANDOMIZED INCREMENTAL ALGORITHM FOR COMPUTING HIGHER ORDER VORONOI DIAGRAMS
- Title not available (Why is that?)
- The Clarkson–Shor Technique Revisited and Extended
- Computational geometry. Algorithms and applications.
- A deterministic view of random sampling and its use in geometry
- On the definition and computation of rectilinear convex hulls
- On Finding the Maxima of a Set of Vectors
- Maxima in hypercubes
- Four results on randomized incremental constructions
- Title not available (Why is that?)
- Geometric approximation algorithms
- On the variance of random polytopes
- Title not available (Why is that?)
- Poisson polytopes
- Threshold phenomena in \(k\)-dominant skylines of random samples
- On the Average Number of Maxima in a Set of Vectors and Applications
- Title not available (Why is that?)
- Computing Many Faces in Arrangements of Lines and Segments
- On the Complexity of Randomly Weighted Voronoi Diagrams
- Union of random Minkowski sums and network vulnerability analysis
- Nearest-Neighbor Searching Under Uncertainty II
- Title not available (Why is that?)
Cited In (6)
- Effectiveness-based Voronoi partition: a new tool for solving a class of location optimization problems
- Union of hypercubes and 3D Minkowski sums with random sizes
- Title not available (Why is that?)
- Some Voronoi diagrams that consider consumer behavior analysis
- Linear expected complexity for directional and multiplicative Voronoi diagrams
- Union of Hypercubes and 3D Minkowski Sums with Random Sizes.
Uses Software
This page was built for publication: From proximity to utility: a Voronoi partition of Pareto optima
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q331376)
