{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:42:59Z","timestamp":1725486179488},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540430025"},{"type":"electronic","value":"9783540452942"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45294-x_16","type":"book-chapter","created":{"date-parts":[[2007,6,11]],"date-time":"2007-06-11T22:45:12Z","timestamp":1181601912000},"page":"183-194","source":"Crossref","is-referenced-by-count":1,"title":["Optimal, Output-Sensitive Algorithms for Constructing Upper Envelope of Line Segments in Parallel"],"prefix":"10.1007","author":[{"given":"Neelima","family":"Gupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sumit","family":"Chopra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sandeep","family":"Sen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,11,26]]},"reference":[{"key":"16_CR1","unstructured":"A. Aggarwal, B. Chazelle, L. Guibas, C. O\u2019Dunlaing and C. K. Yap, Parallel computational geometry. in: Proc. 25th Annual Sympos. Found. Comput. Sci. (1985) 468\u2013477; also: Algorithmica 3 (3) (1988) 293\u2013327."},{"key":"16_CR2","unstructured":"P. K. Aggarwal and M. Sharir, Davenport-Schinzel Sequences and their Geometric Applications. (1995)."},{"issue":"1","key":"16_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02243071","volume":"33","author":"S. Akl","year":"1984","unstructured":"S. Akl, Optimal algorithms for computing convex hulls and sorting, Computing 33 (1) (1984) 1\u201311.","journal-title":"Computing"},{"key":"16_CR4","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).","DOI":"10.1006\/inco.1995.1159"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1006\/jagm.1997.0869","volume":"25","author":"B. K. Bhattacharya","year":"1997","unstructured":"B. K. Bhattacharya and S. Sen, On simple, practical, optimal, output-sensitive randomized planar convex hull algorithm, J. Algorithms 25 (1997) 177\u2013193.","journal-title":"J. Algorithms"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BF02122778","volume":"10","author":"B. Chazelle","year":"1990","unstructured":"B. Chazelle and J. Fredman, A deterministic view of random sampling and its use in geometry, Combinatorica 10 (3) (1990) 229\u2013249.","journal-title":"Combinatorica"},{"key":"16_CR7","unstructured":"W. Chen and K. Wada, On computing the upper envelope of segments in parallel, Proc. International Conference on Parallel Processing. (1998)."},{"key":"16_CR8","unstructured":"K. L. Clarkson, A randomized algorithm for computing a face in an arrangement of line segments."},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. L. Clarkson","year":"1989","unstructured":"K. L. Clarkson and P. W. Shor, Applications of random sampling in computational geometry, II, Discrete Comput. Geom. 4 (1989) 387\u2013421.","journal-title":"Discrete Comput. Geom."},{"key":"16_CR10","unstructured":"M. Goodrich, Geometric partitioning made easier, even in parallel, in: Proc. 9th ACM Sympos. Comput. Geom. (1993) 73\u201382."},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/BF02187744","volume":"4","author":"L. J. Guibas","year":"1989","unstructured":"L. J. Guibas, M. Sharir, and S. Sifrony, On the general motion planning problem with two degrees of freedom, Discrete Comput. Geom., 4 (1989), 491\u2013521","journal-title":"Discrete Comput. Geom."},{"key":"16_CR12","unstructured":"N. Gupta, Efficient Parallel Output-Size Sensitive Algorithms, Ph.D. Thesis, Department of Computer Science and Engineering, Indian Institute of Technology, Delhi (1998)."},{"key":"16_CR13","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, Comput. Geom. Theory and App. 8 (1997) 151\u2013166.","journal-title":"Comput. Geom. Theory and App."},{"key":"16_CR14","unstructured":"N. Gupta and S. Sen, Faster output-sensitive parallel convex hull for d \u2264 3: optimal sub-logarithmic algorithms for small outputs, in: Proc. ACM Sympos. Comput. Geom. (1996) 176\u2013185."},{"key":"16_CR15","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(89)90136-1","volume":"33","author":"J. Hershberger","year":"1989","unstructured":"J. Hershberger, Finding the upper envelope of n line segments in O(n log n) time, Inform. Process. Lett. 33 (1989) 169\u2013174.","journal-title":"Inform. Process. Lett."},{"key":"16_CR16","volume-title":"Computational Geometry: An Introduction through Randomized Algorithms","author":"M. Ketan","year":"1994","unstructured":"M. Ketan, Computational Geometry: An Introduction through Randomized Algorithms. Prentice Hall, EnglewoodCliffs, NJ, (1994)."},{"key":"16_CR17","unstructured":"F. Neilsen and M. Yvinec, An output-sensitive convex hull algorithm for convex objects. Institut National De Recherche En Informatique Et En Automatique. (1995)."},{"key":"16_CR18","volume-title":"Random Sampling Techniques and Parallel Algorithm Design","author":"S. Rajasekaran","year":"1993","unstructured":"S. Rajasekaran and S. Sen, in: J. H. Reif, Ed., Random Sampling Techniques and Parallel Algorithm Design (Morgan Kaufmann Publishers, San Mateo, CA, 1993)."},{"key":"16_CR19","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1137\/S0097539790184298","volume":"23","author":"J. H. Reif","year":"1994","unstructured":"J. H. Reif and S. Sen, Randomized algorithms for binary search and Load Balancing on fixedconnection networks with geometric applications, SIAM J. Comput. 23 (3) (1994) 633\u2013651.","journal-title":"SIAM J. Comput."},{"key":"16_CR20","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1137\/0221031","volume":"21","author":"J. H. Reif","year":"1992","unstructured":"J. H. Reif and S. Sen, optimal parallel randomized algorithms for 3-D convex hull, and related problems, SIAM J. Comput. 21 (1992) 466\u2013485.","journal-title":"SIAM J. Comput."},{"key":"16_CR21","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0304-3975(96)00212-5","volume":"188","author":"S. Sen","year":"1997","unstructured":"S. Sen, Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems, Theoretical Computer Science. 188 (1997) 59\u201378.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45294-X_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T21:28:02Z","timestamp":1556486882000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45294-X_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540430025","9783540452942"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-45294-x_16","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}