Maxima in convex regions

Mordecai J. Golin

Maxima in convex regions

Mordecai J. Golin^*

^*Corresponding author for this work

Research output: Contribution to conference › Conference Paper › peer-review

6 Citations (Scopus)

Abstract

Suppose that C is a bounded convex region. Let p₁,...,p_n be points drawn from the uniform distribution over C and let M_n^C be the number of the points which are maximal. In this note we examine the asymptotics of E(M_n^C) as n→∞. We show, for example, that if C is planar then, either E(M_n^C) = Θ(√n) or E(M_n^C) = O(log n), and give a simple geometric criterion that tells which of the two behaviors applies. This note also addresses the asymptotics of E(M_n^C) when C is a higher-dimensional convex region, and discusses the asymptotic behavior of the higher moments of M_n^C as well. Some immediate algorithmic implications that follow from knowing E(M_n^C) are also examined, e.g., the existence of heuristics for finding maxima that have fast expected running times when their input points are drawn from any of many different possible distributions.

Original language	English
Pages	352-360
Number of pages	9
Publication status	Published - 1993
Externally published	Yes
Event	Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA Duration: 25 Jan 1993 → 27 Jan 1993

Conference

Conference	Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
City	Austin, TX, USA
Period	25/01/93 → 27/01/93

Cite this

@conference{89b11f30b9164bdaa93c96b29f774818,

title = "Maxima in convex regions",

abstract = "Suppose that C is a bounded convex region. Let p1,...,pn be points drawn from the uniform distribution over C and let MnC be the number of the points which are maximal. In this note we examine the asymptotics of E(MnC) as n→∞. We show, for example, that if C is planar then, either E(MnC) = Θ(√n) or E(MnC) = O(log n), and give a simple geometric criterion that tells which of the two behaviors applies. This note also addresses the asymptotics of E(MnC) when C is a higher-dimensional convex region, and discusses the asymptotic behavior of the higher moments of MnC as well. Some immediate algorithmic implications that follow from knowing E(MnC) are also examined, e.g., the existence of heuristics for finding maxima that have fast expected running times when their input points are drawn from any of many different possible distributions.",

author = "Golin, \{Mordecai J.\}",

year = "1993",

language = "English",

pages = "352--360",

note = "Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 25-01-1993 Through 27-01-1993",

}

TY - CONF

T1 - Maxima in convex regions

AU - Golin, Mordecai J.

PY - 1993

Y1 - 1993

N2 - Suppose that C is a bounded convex region. Let p1,...,pn be points drawn from the uniform distribution over C and let MnC be the number of the points which are maximal. In this note we examine the asymptotics of E(MnC) as n→∞. We show, for example, that if C is planar then, either E(MnC) = Θ(√n) or E(MnC) = O(log n), and give a simple geometric criterion that tells which of the two behaviors applies. This note also addresses the asymptotics of E(MnC) when C is a higher-dimensional convex region, and discusses the asymptotic behavior of the higher moments of MnC as well. Some immediate algorithmic implications that follow from knowing E(MnC) are also examined, e.g., the existence of heuristics for finding maxima that have fast expected running times when their input points are drawn from any of many different possible distributions.

AB - Suppose that C is a bounded convex region. Let p1,...,pn be points drawn from the uniform distribution over C and let MnC be the number of the points which are maximal. In this note we examine the asymptotics of E(MnC) as n→∞. We show, for example, that if C is planar then, either E(MnC) = Θ(√n) or E(MnC) = O(log n), and give a simple geometric criterion that tells which of the two behaviors applies. This note also addresses the asymptotics of E(MnC) when C is a higher-dimensional convex region, and discusses the asymptotic behavior of the higher moments of MnC as well. Some immediate algorithmic implications that follow from knowing E(MnC) are also examined, e.g., the existence of heuristics for finding maxima that have fast expected running times when their input points are drawn from any of many different possible distributions.

UR - https://www.scopus.com/pages/publications/0027147829

M3 - Conference Paper

AN - SCOPUS:0027147829

SP - 352

EP - 360

T2 - Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 25 January 1993 through 27 January 1993

ER -

Maxima in convex regions

Abstract

Conference

Other files and links

Fingerprint

Cite this