{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T05:05:00Z","timestamp":1743138300944,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540646822"},{"type":"electronic","value":"9783540691068"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0054380","type":"book-chapter","created":{"date-parts":[[2006,6,7]],"date-time":"2006-06-07T07:43:28Z","timestamp":1149666208000},"page":"335-346","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Distribution-sensitive algorithms"],"prefix":"10.1007","author":[{"given":"Sandeep","family":"Sen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neelima","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,5,26]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"H Bast and T Hagerup. Fast parallel space allocation,estimation and integer sorting. Technical Report, MPI-I-93-123, June 1993.","key":"31_CR1","DOI":"10.1006\/inco.1995.1159"},{"doi-asserted-by":"crossref","unstructured":"M. Ben-Or Lower bounds for algebraic computation trees. Proc. of the 15th ACM STOC, pp. 80\u201386, 1983.","key":"31_CR2","DOI":"10.1145\/800061.808735"},{"key":"31_CR3","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1006\/jagm.1997.0869","volume":"25","author":"B. Bhattacharya","year":"1997","unstructured":"B. Bhattacharya and S. Sen. On a simple, practical, optimal, output-sensitive randomized planar convex-hull algorithm. Journal of Algorithms, 25, pp. 177\u2013193, 1997.","journal-title":"Journal of Algorithms"},{"doi-asserted-by":"crossref","unstructured":"T.M. Chan. Output-Sensitive Results on convex hulls, extreme points and related problems. ACM Symp. on Comput. Geom., 1995.","key":"31_CR4","DOI":"10.1145\/220279.220281"},{"unstructured":"Timothy.M.Y. Chan, Jack Snoeyink, Chee-Keng Yap. Output-Sensitive Construction of Polytopes in Four Dimensions and Clipped Voronoi Diagrams in Three. Proc. 6th ACM-SIAM Sympos. Discrete Algorithms 1995, pp 282\u2013291.","key":"31_CR5"},{"issue":"1","key":"31_CR6","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1137\/0213003","volume":"13","author":"M. Dyer","year":"1984","unstructured":"M. Dyer Linear time algorithms for two and three variable linear programs. SIAM Journal on Computing, 13(1), pp. 31\u201345, 1984.","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Farach and Muthukrishnan. Optimal parallel randomized renaming. Information Processing Letters, pp. 12\u201315, Jan 1997.","key":"31_CR7","DOI":"10.1016\/S0020-0190(96)00182-2"},{"key":"31_CR8","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R. L. Graham","year":"1972","unstructured":"R L Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Proc. Lett., 1:132\u2013133, 1972.","journal-title":"Information Proc. Lett."},{"key":"31_CR9","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/S0925-7721(97)00009-6","volume":"8","author":"N. Gupta","year":"1997","unstructured":"N. Gupta and S. Sen. Optimal, output-sensitive algorithms for constructing planar hulls in parallel. Computational Geometry: Theory and Applications, 8, 151\u2013166, 1997.","journal-title":"Computational Geometry: Theory and Applications"},{"unstructured":"T. Hagerup. Fast deterministic processor allocation. Proc. of the 4th ACM Symposium on Discrete Algorithms 1993, pp. 1\u201310.","key":"31_CR10"},{"unstructured":"T. Goldberg and U. Zwick. Optimal Deterministic Approximate Parallel Prefix Sums and Their Applications. In Proc. Israel Symp. on Theory and Computing Systems (ISTCS'95), (1995), pp. 220\u2013228.","key":"31_CR11"},{"doi-asserted-by":"crossref","unstructured":"S. Kapoor and P. Ramanan. Lower bounds for maximal and convex layer problems. Algorithmica, pages 447\u2013459, 1989.","key":"31_CR12","DOI":"10.1007\/BF01553901"},{"issue":"1","key":"31_CR13","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1137\/0215021","volume":"15","author":"D. G. Kirkpatrick","year":"1986","unstructured":"D G Kirkpatrick and R Seidel. The ultimate planar convex hull algorithm. SIAM Jl. of Comput., 15(1):287\u2013299, Feb. 1986.","journal-title":"SIAM Jl. of Comput."},{"doi-asserted-by":"crossref","unstructured":"D G Kirkpatrick and R Seidel. Output-Size sensitive algorithms for finding maximal vectors. Proc. of ACM Symp. on Computational Geometry 1985, pp. 89\u201396.","key":"31_CR14","DOI":"10.1145\/323233.323246"},{"key":"31_CR15","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1145\/321906.321910","volume":"22","author":"H.T. Kung","year":"1975","unstructured":"H.T. Kung, F. Luccio and F.P. Preparata. On finding the maxima of a set of vectors. Journal of the ACM, 22, pp. 469\u2013476, 1975.","journal-title":"Journal of the ACM"},{"unstructured":"P. D. MacKenzie. Load balancing requires \u03a9(log *n) expected time. Symp. on Discrete Algorithms, pp. 94\u201399, 1992.","key":"31_CR16"},{"issue":"4","key":"31_CR17","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1137\/0212052","volume":"12","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo Linear time algorithms for linear programming in R3 and related problems. SIAM Journal on Computing 12(4), pp. 759\u2013776, 1983.","journal-title":"SIAM Journal on Computing"},{"key":"31_CR18","first-page":"473","volume":"519","author":"I.J. Munro","year":"1991","unstructured":"I.J. Munro and V. Raman. Sorting multisets and vectors In-place. Proc. of the 2nd WADS, LNCS 519, pp. 473\u2013479, 1991.","journal-title":"LNCS"},{"issue":"1","key":"31_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0205001","volume":"5","author":"I. Munro","year":"1976","unstructured":"I. Munro and P.M. Spira Sorting and Searching in Multisets. SIAM journal on Computing, 5(1), pp. 1\u20138, 1976.","journal-title":"SIAM journal on Computing"},{"key":"31_CR20","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1145\/359423.359430","volume":"20","author":"F. P. Preparata","year":"1977","unstructured":"F P Preparata and S J Hong. Convex hulls of finite sets of points in two and three dimensions. Comm. ACM, 20:87\u201393, 1977.","journal-title":"Comm. ACM"},{"key":"31_CR21","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F P Preparata and M I Shamos. Computational Geometry: An Introduction. Springer-verlag, New York, 1985."},{"unstructured":"S. Rajasekaran and S. Sen. Random sampling Techniques and parallel algorithm design. J.H. Reif editor. Morgan, Kaufman Publishers, 1993.","key":"31_CR22"},{"issue":"5","key":"31_CR23","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0020-0190(82)90118-1","volume":"15","author":"L.M. Wenger","year":"1982","unstructured":"L.M. Wenger. Sorting a linked list with equal keys. Information Processing Letters, 15(5), pp. 205\u2013208, 1982.","journal-title":"Information Processing Letters"},{"unstructured":"R. Wenger. Randomized Quick Hull. to appear in Algorithmica.","key":"31_CR24"},{"key":"31_CR25","doi-asserted-by":"publisher","first-page":"780","DOI":"10.1145\/322276.322289","volume":"28","author":"A.C. Yao","year":"1981","unstructured":"A.C. Yao A lower bound to finding convex hulls. Journal of the ACM, 28, pp. 780\u2013787, 1981.","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'98"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0054380","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T20:12:59Z","timestamp":1675714379000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BFb0054380"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540646822","9783540691068"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/bfb0054380","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]},"assertion":[{"value":"26 May 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}