{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,5]],"date-time":"2026-11-05T03:49:21Z","timestamp":1793850561625,"version":"4.6.1"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,5]]},"abstract":"<jats:p>Let D be a dynamic set of ordered pairs $[ x,y ]$ over the set $0,1, \\cdots ,k - 1$ of integers. Consider the following operations applied to D: (1) Insert (delete) a pair $[ x,y ]$ into (from) D. (2) Given test integers $x0,x1$, and $y1$, among all pairs $[ x,y ]$ in D such that $x0 \\leqq x \\leqq x1$ and $y \\leqq y1$, find a pair whose x is minimal (or maximal). (3) Given test integers $x0$ and $x1$, among all pairs $[ x,y ]$ in D such that $x0 \\leqq x \\leqq x1$, find a pair whose y is minimal. (4) Given test integers $x0$, $x1$, and $y1$, enumerate those pairs $[x,y ]$ in D such that $x0 \\leqq x \\leqq x1$ and $y \\leqq y1$.<\/jats:p>\n                  <jats:p>Using a new data structure that we call a priority search tree, of which two variants are introduced, operations (1), (2), and (3) can be implemented in $O(\\log n)$ time, where n is the cardinality of D. Operation (4) is performed in at most $O(\\log n + s)$ time, where s is the number of pairs enumerated. The priority search tree occupies $O(n)$ space.<\/jats:p>\n                  <jats:p>Priority seach tree algorithms can be used effectively as subroutines in diverse applications. With them one can answer questions of intersection or containment in a dynamic set of linear intervals. They can be used in combination with a well-known plane-sweep technique, to implement off-line algorithms for enumerating all intersecting pairs of rectangles. Priority search trees can also be used to implement best-\/first-fit storage allocation.<\/jats:p>","DOI":"10.1137\/0214021","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"257-276","source":"Crossref","is-referenced-by-count":341,"title":["Priority Search Trees"],"prefix":"10.1137","volume":"14","author":[{"given":"Edward M.","family":"McCreight","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","unstructured":"Donald E. Knuth, The art of computer programming. Volume 3, Addison-Wesley Publishing Co., Reading, Mass.London-Don Mills, Ont., 1973, 142\u2013145, Sorting and Searching56:4281"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1982160100511"},{"key":"R3","unstructured":"E. Mccreight,  Efficient algorithms for enumerating intersecting intervals and rectangles, Technical Report, CSL-80-9, Xerox Palo Alto Research Center, Xerox Corporation, Palo Alto Research Center, 3333 Coyote Hill Road, Palo Alto, CA,  1980"},{"key":"R4","unstructured":"L. Guibas, J. Saxe,  1980, Private communication"},{"key":"R5","unstructured":"H. Edelsbrunner,  Dynamic rectangle intersection searching, Report, 47, Information Processing Institute, Technical University of Graz, Graz, Austria,  1980, February"},{"key":"R6","unstructured":"H. Edelsbrunner,  Dynamic data structures for orthogonal intersection queries, Report, 59, Information Processing Institute, Technical University of Graz, Graz, Austria,  1980, October"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Michael Ian Shamos, Dan Hoey,  Geometric intersection problems,  17th Annual Symposium on Foundations of Computer Science (Houston, Tex., 1976), IEEE Comput. Soc., Long Beach, Calif.,  1976,  208\u2013215 56:13770","DOI":"10.1109\/SFCS.1976.16"},{"key":"R8","unstructured":"H. Edelsbrunner,  A time- and space-optimal solution for the planar all intersecting rectangles problem, Report, 50, Information Processing Institute, Technical University of Graz, Graz, Austria,  1980, April"},{"key":"R9","first-page":"7","volume-title":"Bulletin of the European Association of Theoretical Computer Science, #9","author":"Bentley J.","year":"1979"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1980.1675628"},{"key":"R11","unstructured":"R. P. Brent,  Efficient implementation of the first-fit strategy for dynamic storage allocation, TR-CS-81-05, Dept. Computer Science, Australian National University, Canberra, ACT 2600, Australia, 1981, Australian Computer Science Communications, to appear"},{"key":"R12","unstructured":"J. Nievergelt, F. P. Preparata,  Plane-sweep algorithms for interesting geometric figures, Technical Report in preparation, Institut f\u00fcr Informatik, ETH, Zurich"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/358841.358852"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289509"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.3"},{"key":"R16","unstructured":"R. Tarjan,  1982, Private communication, September"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214021","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:42:42Z","timestamp":1787337762000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214021"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,5]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1985,5]]}},"alternative-id":["10.1137\/0214021"],"URL":"https:\/\/doi.org\/10.1137\/0214021","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,5]]}}}