{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,23]],"date-time":"2024-09-23T03:45:27Z","timestamp":1727063127621},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1991,9,1]],"date-time":"1991-09-01T00:00:00Z","timestamp":683683200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1991,9]]},"DOI":"10.1007\/bf02574692","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T14:31:20Z","timestamp":1174573880000},"page":"307-338","source":"Crossref","is-referenced-by-count":49,"title":["On levels in arrangements and voronoi diagrams"],"prefix":"10.1007","volume":"6","author":[{"given":"Ketan","family":"Mulmuley","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,6,26]]},"reference":[{"key":"BF02574692_CR1","doi-asserted-by":"crossref","unstructured":"A. Agarwal, L. Guibas, S. Saxe, P. Shor, A linear time algorithm for computing the Voronoi diagram of a convex polygon,Proceedings of the Annual ACM Symposium on Theory of Computing, 1987, pp. 39\u201345.","DOI":"10.1145\/28395.28400"},{"key":"BF02574692_CR2","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1016\/0097-3165(86)90122-6","volume":"41","author":"N. Alon","year":"1986","unstructured":"N. Alon, E. Gyori, The number of small semispaces of a finite set of points in the plane,J. Combin. Theory Ser. A 41 (1986), 154\u2013157.","journal-title":"J. Combin. Theory Ser. A"},{"key":"BF02574692_CR3","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0020-0190(79)90074-7","volume":"9","author":"K. Brown","year":"1979","unstructured":"K. Brown, Voronoi diagrams from convex hulls,Inform. Process. Lett. 9 (1979), 223\u2013228.","journal-title":"Inform. Process. Lett."},{"key":"BF02574692_CR4","doi-asserted-by":"crossref","unstructured":"B. Chazelle, H. Edelsbrunner, An improved algorithm for constructingk-th order Voronoi diagram,Proceedings of the Annual Symposium on Computational Geometry, 1985, pp. 228\u2013234.","DOI":"10.1145\/323233.323263"},{"key":"BF02574692_CR5","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02187685","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"B. Chazelle, F. Preparata, Halfspace range search: an algorithmic application ofk-sets,Discrete Comput. Geom. 1 (1986), 83\u201393.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574692_CR6","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K. Clarkson","year":"1987","unstructured":"K. Clarkson, New applications of random sampling in computational geometry,Discrete Comput. Geom. 2 (1987), 195\u2013222.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574692_CR7","doi-asserted-by":"crossref","unstructured":"K. Clarkson, Applications of random sampling in computational geometry, II,Proceedings of the Annual Symposium on Computational Geometry, 1988, pp. 1\u201311.","DOI":"10.1145\/73393.73394"},{"key":"BF02574692_CR8","doi-asserted-by":"crossref","unstructured":"K. Clarkson, P. Shor, Algorithms for diametral pairs and convex hulls that are optimal randomized, and incremental,Proceedings of the Annual Symposium on Computational Geometry, 1988, pp. 12\u201317.","DOI":"10.1145\/73393.73395"},{"key":"BF02574692_CR9","doi-asserted-by":"crossref","unstructured":"R. Cole, M. Sharir, C. Yap, Onk-hulls and related problems,Proceedings of the 16th Annual SIGACT Symposium, 1984, pp. 154\u2013166.","DOI":"10.1145\/800057.808677"},{"key":"BF02574692_CR10","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/BF01840438","volume":"1","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, Edge skeletons in arrangements with applications,Algorithmica 1 (1986), 93\u2013109.","journal-title":"Algorithmica"},{"key":"BF02574692_CR11","unstructured":"H. Edelsbrunner, Private communication."},{"key":"BF02574692_CR12","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, J. O'Rourke, R. Seidel, Constructing arrangements of lines and hyperplanes with applications,SIAM J. Comput. 15 (1986), 341\u2013363.","journal-title":"SIAM J. Comput."},{"key":"BF02574692_CR13","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF02187681","volume":"1","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, R. Seidel, Voronoi diagrams and arrangments,Discrete Comput. Geom. 1 (1986), 25\u201344.","journal-title":"Discrete Comput. Geom."},{"key":"BF02574692_CR14","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/B978-0-7204-2262-7.50018-1","volume-title":"A Survey of Combinatorial Theory","author":"P. Erd\u00f6s","year":"1973","unstructured":"P. Erd\u00f6s, L. Lov\u00e1sz, A. Simmons, E. Strauss, Dissection graphs of planar point sets, inA Survey of Combinatorial Theory, J. N. Srivastava,et al., eds., North-Holland, Amsterdam, 1973, pp. 139\u2013149."},{"key":"BF02574692_CR15","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/0097-3165(84)90081-5","volume":"36","author":"J. E. Goodman","year":"1984","unstructured":"J. E. Goodman, R. Pollack, On the number ofk-subsets of a set ofn points in the plane,J. Combin. Theory Ser. A 36 (1984), 101\u2013104.","journal-title":"J. Combin. Theory Ser. A"},{"key":"BF02574692_CR16","volume-title":"The Art of Computer Programming","author":"D. Knuth","year":"1969","unstructured":"D. Knuth,The Art of Computer Programming, Vol. 2, Addison Wesley, Reading, MA, 1969."},{"key":"BF02574692_CR17","first-page":"478","volume":"31","author":"D. Lee","year":"1982","unstructured":"D. Lee, Onk-nearest neighbour Voronoi diagrams in the plane,IEEE Trans. Comput. 31 (1982), 478\u2013487.","journal-title":"IEEE Trans. Comput."},{"key":"BF02574692_CR18","doi-asserted-by":"crossref","unstructured":"K. Mulmuley, A fast planar partition algorithm, I,Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988, pp. 580\u2013589. Full version to appear inJ. Symbolic Logic, a special issue on Computational Geometry.","DOI":"10.1109\/SFCS.1988.21974"},{"key":"BF02574692_CR19","doi-asserted-by":"crossref","unstructured":"K. Mulmuley, A fast planar partition algorithm, II,Proceedings of the Fifth ACM Annual Symposium on Computational Geometry, 1989, pp. 33\u201343. To appear inJ. Assoc. Comput. Mach.","DOI":"10.1145\/73833.73837"},{"issue":"3","key":"BF02574692_CR20","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1145\/74334.74372","volume":"23","author":"K. Mulmuley","year":"1989","unstructured":"K. Mulmuley, An efficient algorithm for hidden surface removal,Computer Graphics 23(3) (1989), 379\u2013388.","journal-title":"Computer Graphics"},{"key":"BF02574692_CR21","doi-asserted-by":"crossref","unstructured":"K. Mulmuley, An efficient algorithm for hidden surface removal, II, Technical Report, University of Chicago, August 1989, Invited for publication inJ. Algorithms. (Also see On obstructions in relation to a fixed viewpoint,Proceedings of the 30th Annual Symposium on Foundations of Computer Science, 1989, pp. 592\u2013597.)","DOI":"10.1109\/SFCS.1989.63540"},{"key":"BF02574692_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"F. Preparata","year":"1985","unstructured":"F. Preparata, M. Shamos,Computational Geometry, Springer-Verlag, New York, 1985."},{"key":"BF02574692_CR23","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF02187686","volume":"1","author":"E. Welzl","year":"1986","unstructured":"E. Welzl, More onk-sets of finite sets in the plane,Discrete Comput. Geom. 1 (1986), 95\u2013100.","journal-title":"Discrete Comput. Geom."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574692.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02574692\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02574692","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T16:30:33Z","timestamp":1558197033000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02574692"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,9]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1991,9]]}},"alternative-id":["BF02574692"],"URL":"https:\/\/doi.org\/10.1007\/bf02574692","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,9]]}}}