Go to the content (press return)

# FUTUR. Website for the scientific production of UPC researchers

## Smoothed analysis of the expected number of maximal points in two dimensions

Author
Diaz, J.; Golin, M.
Type of activity
Report
Date
2018-07-18
Project funding
Graph-based Models and Methods for Computing in the Large
URL
https://arxiv.org/pdf/1807.06845.pdf
Abstract
The {\em Maximal} points in a set S are those that aren't {\em dominated} by any other point in S. Such points arise in multiple application settings in which they are called by a variety of different names, e.g., maxima, Pareto optimums, skylines. Because of their ubiquity, there is a large literature on the {\em expected} number of maxima in a set S of n points chosen IID from some distribution. Most such results assume that the underlying distribution is uniform over some spatial region and s...
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods