From proximity to utility: a Voronoi partition of Pareto optima
From MaRDI portal
(Redirected from Publication:331376)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 431985 (Why is no real title available?)
- scientific article; zbMATH DE number 480263 (Why is no real title available?)
- scientific article; zbMATH DE number 480264 (Why is no real title available?)
- scientific article; zbMATH DE number 732977 (Why is no real title available?)
- A SIMPLE ON-LINE RANDOMIZED INCREMENTAL ALGORITHM FOR COMPUTING HIGHER ORDER VORONOI DIAGRAMS
- A deterministic view of random sampling and its use in geometry
- Applications of random sampling in computational geometry. II
- Computational geometry. Algorithms and applications.
- Computing Many Faces in Arrangements of Lines and Segments
- Four results on randomized incremental constructions
- From proximity to utility: a Voronoi partition of Pareto optima
- Geometric approximation algorithms
- Maxima in hypercubes
- Nearest-neighbor searching under uncertainty. II
- On Finding the Maxima of a Set of Vectors
- On the Average Number of Maxima in a Set of Vectors and Applications
- On the Complexity of Randomly Weighted Voronoi Diagrams
- On the definition and computation of rectilinear convex hulls
- On the variance of random polytopes
- Poisson polytopes
- The Clarkson–Shor Technique Revisited and Extended
- Threshold phenomena in \(k\)-dominant skylines of random samples
- Union of random Minkowski sums and network vulnerability analysis
- Voronoi diagrams and Delaunay triangulations
- \(\epsilon\)-nets and simplex range queries
Cited in
(8)- 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
- Separating a Voronoi diagram via local search
- Union of hypercubes and 3D Minkowski sums with random sizes
- Some Voronoi diagrams that consider consumer behavior analysis
- scientific article; zbMATH DE number 7651184 (Why is no real title available?)
- Linear expected complexity for directional and multiplicative Voronoi diagrams
- From proximity to utility: a Voronoi partition of Pareto optima
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)
