{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:40:21Z","timestamp":1787388021095,"version":"build-2736575974"},"reference-count":9,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[1992,2]]},"abstract":"<jats:p>The set maxima problem is as follows: given a family of subsets $\\mathcal{S}$ of a totally ordered set $X = \\{ x_1 , \\cdots ,x_n \\}$, find the maximum in each subset. The computational model is the comparison tree. One possible solution is to sort the set X, which requires $O( n \\log n )$ comparisons. The open question is whether set maxima is easier than sorting.<\/jats:p>\n                  <jats:p>Here, a solution is presented that requires a linear number of comparisons for the following two cases: \u2022 The sets are hyperplanes in a d-dimensional projective geometry $PG ( d,q )$. In particular, the interesting case is $PG ( 2,q )$, when the intersection of any two subsets is exactly one. \u2022 The sets are chosen randomly with probability $p ( n )$ for each element to be in a set. The random choices are mutually independent and the number of comparisons needed is linear with probability approaching 1 asymptotically.<\/jats:p>","DOI":"10.1137\/0405001","type":"journal-article","created":{"date-parts":[[2005,2,23]],"date-time":"2005-02-23T08:04:07Z","timestamp":1109145847000},"page":"1-9","source":"Crossref","is-referenced-by-count":3,"title":["A Linear Time Approach to the Set Maxima Problem"],"prefix":"10.1137","volume":"5","author":[{"given":"Amotz","family":"Bar-Noy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajeev","family":"Motwan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph","family":"Naor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,8]]},"reference":[{"key":"R1","volume-title":"The design and analysis of computer algorithms","author":"Aho Alfred V.","year":"1975"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579382"},{"key":"R3","volume-title":"Combinatorics of finite geometries","author":"Batten Lynn Margaret","year":"1986"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"W. Goddard, V. King, L. Schulman, Optimal randomized algorithms for local sorting and set maxima, Proc. 22nd Annual Symposium on Theory of Computing, 1990, 45\u201353","DOI":"10.1145\/100216.100222"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/322203.322206"},{"key":"R6","volume-title":"An introduction to probability theory and its applications. Vol. I","author":"Feller William","year":"1968"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579443"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"C. Kenyon-Mathieu, V. King, Verifying partial orders, Proc. 21st Annual ACM Symposium on Theory of Computing, 1989, 367\u2013374","DOI":"10.1145\/73007.73042"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010102"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0405001","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:26:32Z","timestamp":1787318792000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0405001"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,2]]},"references-count":9,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1992,2]]}},"alternative-id":["10.1137\/0405001"],"URL":"https:\/\/doi.org\/10.1137\/0405001","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,2]]}}}