On the average number of maximal in a set of vectors.

*(English)*Zbl 0682.68041Summary: Any of n vectors in d-space is called maximal if none of the remaining vectors dominates it in every component. Assuming that n vectors are distributed identically and that the d components of each vector are distributed independently and continuously, we determine the expected number of maximal vectors explicitly for any n and d. The asymptotic behaviour of this quantity as n tends to infinity, which was investigated by Bentley, Kung, Schkolnick, Thompson and Devroye, follows immediately from our result.

##### MSC:

68Q25 | Analysis of algorithms and problem complexity |

##### Keywords:

geometric probability; maxima of a set of vectors; probabilistic analysis of algorithms; random points; average number of maxima
PDF
BibTeX
XML
Cite

\textit{C. Buchta}, Inf. Process. Lett. 33, No. 2, 63--65 (1989; Zbl 0682.68041)

Full Text:
DOI

##### References:

[1] | Bentley, J.L.; Kung, H.T.; Schkolnick, M.; Thompson, C.D., On the average number of maxima in a set of vectors and applications, J. ACM, 25, 536-543, (1978) · Zbl 0388.68056 |

[2] | Bentley, J.L.; Shamos, M.I., Divide and conquer for linear expected time, Inform. process. lett., 7, 87-91, (1978) · Zbl 0404.68046 |

[3] | Devroye, L., A note on finding convex hulls via maximal vectors, Inform. process. lett., 11, 53-56, (1980) · Zbl 0444.68063 |

[4] | Preparata, F.P.; Shamos, M.I., Computational geometry, (1985), Springer New York · Zbl 0759.68037 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.