{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T22:51:56Z","timestamp":1673304716351},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,3,25]],"date-time":"2011-03-25T00:00:00Z","timestamp":1301011200000},"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":[[2011,6]]},"DOI":"10.1007\/s00454-011-9346-8","type":"journal-article","created":{"date-parts":[[2011,3,24]],"date-time":"2011-03-24T15:15:59Z","timestamp":1300979759000},"page":"796-823","source":"Crossref","is-referenced-by-count":5,"title":["Computing Hereditary Convex Structures"],"prefix":"10.1007","volume":"45","author":[{"given":"Bernard","family":"Chazelle","sequence":"first","affiliation":[]},{"given":"Wolfgang","family":"Mulzer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,3,25]]},"reference":[{"issue":"6","key":"9346_CR1","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/BF02187749","volume":"4","author":"A. Aggarwal","year":"1989","unstructured":"Aggarwal, A., Guibas, L.J., Saxe, J., Shor, P.W.: A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete Comput. Geom. 4(6), 591\u2013604 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"9346_CR2","first-page":"201","volume-title":"Proc. 16th Annu. ACM Sympos. Comput. Geom. (SoCG)","author":"N.M. Amato","year":"2000","unstructured":"Amato, N.M., Goodrich, M.T., Ramos, E.A.: Linear-time triangulation of a simple polygon made easier via randomization. In: Proc. 16th Annu. ACM Sympos. Comput. Geom. (SoCG), pp. 201\u2013212 (2000)"},{"issue":"4","key":"9346_CR3","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1142\/S0218195994000252","volume":"4","author":"R. Bar-Yehuda","year":"1994","unstructured":"Bar-Yehuda, R., Chazelle, B.: Triangulating disjoint Jordan chains. Int. J. Comput. Geom. Appl. 4(4), 475\u2013481 (1994)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9346_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M. Berg de","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"key":"9346_CR5","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139172998","volume-title":"Algorithmic Geometry","author":"J.D. Boissonnat","year":"1998","unstructured":"Boissonnat, J.D., Yvinec, M.: Algorithmic Geometry. Cambridge University Press, New York (1998)"},{"key":"9346_CR6","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1109\/FOCS.2009.53","volume-title":"Proc. 50th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS)","author":"K. Buchin","year":"2009","unstructured":"Buchin, K., Mulzer, W.: Delaunay triangulations in O(sort(n)) time and more. In: Proc. 50th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pp. 139\u2013148 (2009)"},{"issue":"2","key":"9346_CR7","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1137\/S0097539798349188","volume":"30","author":"T.M. Chan","year":"2000","unstructured":"Chan, T.M.: Random sampling, halfspace range reporting, and construction of (\u2264k)-levels in three dimensions. SIAM J. Comput. 30(2), 561\u2013575 (2000)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9346_CR8","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.comgeo.2005.11.002","volume":"35","author":"T.M. Chan","year":"2006","unstructured":"Chan, T.M.: Three problems about simple polygons. Comput. Geom. Theory Appl. 35(3), 209\u2013217 (2006)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"3","key":"9346_CR9","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1137\/0215051","volume":"15","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B.: Filtering search: a new approach to query-answering. SIAM J. Comput. 15(3), 703\u2013724 (1986)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"9346_CR10","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/BF02574703","volume":"6","author":"B. Chazelle","year":"1991","unstructured":"Chazelle, B.: Triangulating a simple polygon in linear time. Discrete Comput. Geom. 6(5), 485\u2013524 (1991)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"9346_CR11","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1137\/0221041","volume":"21","author":"B. Chazelle","year":"1992","unstructured":"Chazelle, B.: An optimal algorithm for intersecting three-dimensional convex polyhedra. SIAM J. Comput. 21(4), 671\u2013696 (1992)","journal-title":"SIAM J. Comput."},{"key":"9346_CR12","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511626371","volume-title":"The Discrepancy Method: Randomness and Complexity","author":"B. Chazelle","year":"2000","unstructured":"Chazelle, B.: The Discrepancy Method: Randomness and Complexity. Cambridge University Press, New York (2000)"},{"issue":"1","key":"9346_CR13","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/s00453-002-0939-8","volume":"34","author":"B. Chazelle","year":"2002","unstructured":"Chazelle, B., Devillers, O., Hurtado, F., Mora, M., Sacrist\u00e1n, V., Teillaud, M.: Splitting a Delaunay triangulation in linear time. Algorithmica 34(1), 39\u201346 (2002)","journal-title":"Algorithmica"},{"key":"9346_CR14","unstructured":"Chew, L.P.: Building Voronoi diagrams for convex polygons in linear expected time. Tech. Rep. PCS-TR90-147, Dartmouth College, Computer Science, Hanover, NH (1990)"},{"issue":"2","key":"9346_CR15","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BF02526034","volume":"18","author":"L.P. Chew","year":"1997","unstructured":"Chew, L.P., Fortune, S.: Sorting helps for Voronoi diagrams. Algorithmica 18(2), 217\u2013228 (1997)","journal-title":"Algorithmica"},{"issue":"3","key":"9346_CR16","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1007\/PL00009429","volume":"21","author":"F. Chin","year":"1999","unstructured":"Chin, F., Snoeyink, J., Wang, C.A.: Finding the medial axis of a simple polygon in linear time. Discrete Comput. Geom. 21(3), 405\u2013420 (1999)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"9346_CR17","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1137\/S0097539795285916","volume":"28","author":"F. Chin","year":"1998","unstructured":"Chin, F., Wang, C.A.: Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear time. SIAM J. Comput. 28(2), 471\u2013486 (1998)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9346_CR18","doi-asserted-by":"crossref","first-page":"830","DOI":"10.1137\/0217052","volume":"17","author":"K.L. Clarkson","year":"1988","unstructured":"Clarkson, K.L.: A randomized algorithm for closest-point queries. SIAM J. Comput. 17(4), 830\u2013847 (1988)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"9346_CR19","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K.L. Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry. II. Discrete Comput. Geom. 4(5), 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"9346_CR20","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"issue":"1","key":"9346_CR21","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1142\/S021819599200007X","volume":"2","author":"O. Devillers","year":"1992","unstructured":"Devillers, O.: Randomization yields simple O(nlog\u2009\u2217 n) algorithms for difficult \u03a9(n) problems. Int. J. Comput. Geom. Appl. 2(1), 97\u2013111 (1992)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"3","key":"9346_CR22","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1142\/S0218195995000192","volume":"5","author":"H.N. Djidjev","year":"1995","unstructured":"Djidjev, H.N., Lingas, A.: On computing Voronoi diagrams for sorted point sets. Int. J. Comput. Geom. Appl. 5(3), 327\u2013337 (1995)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"3","key":"9346_CR23","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0304-3975(82)90120-7","volume":"27","author":"D.P. Dobkin","year":"1983","unstructured":"Dobkin, D.P., Kirkpatrick, D.G.: Fast detection of polyhedral intersection. Theor. Comput. Sci. 27(3), 241\u2013253 (1983)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9346_CR24","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1016\/0196-6774(85)90007-0","volume":"6","author":"D.P. Dobkin","year":"1985","unstructured":"Dobkin, D.P., Kirkpatrick, D.G.: A linear algorithm for determining the separation of convex polyhedra. J. Algorithms 6(3), 381\u2013392 (1985)","journal-title":"J. Algorithms"},{"issue":"3","key":"9346_CR25","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s00453-007-9010-0","volume":"49","author":"H. Fournier","year":"2007","unstructured":"Fournier, H., Vigneron, A.: A tight lower bound for computing the diameter of a 3D convex polytope. Algorithmica 49(3), 245\u2013257 (2007)","journal-title":"Algorithmica"},{"issue":"4","key":"9346_CR26","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/BF02187846","volume":"7","author":"D.G. Kirkpatrick","year":"1992","unstructured":"Kirkpatrick, D.G., Klawe, M.M., Tarjan, R.E.: Polygon triangulation in O(nlog\u2009\u2009log\u2009\u2009n) time with simple data structures. Discrete Comput. Geom. 7(4), 329\u2013346 (1992)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"9346_CR27","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1142\/S0218195996000198","volume":"6","author":"R. Klein","year":"1996","unstructured":"Klein, R., Lingas, A.: A linear-time randomized algorithm for the bounded Voronoi diagram of a simple polygon. Int. J. Comput. Geom. Appl. 6(3), 263\u2013278 (1996)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9346_CR28","first-page":"544","volume-title":"Proc. 19th Annu. Internat. Sympos. Algorithms Comput. (ISAAC)","author":"M.J. Kreveld van","year":"2008","unstructured":"van Kreveld, M.J., L\u00f6ffler, M., Mitchell, J.S.B.: Preprocessing imprecise points and splitting triangulations. In: Proc. 19th Annu. Internat. Sympos. Algorithms Comput. (ISAAC), pp. 544\u2013555 (2008)"},{"key":"9346_CR29","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J. Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol.\u00a0212. Springer, New York (2002)"},{"key":"9346_CR30","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"K. Mulmuley","year":"1994","unstructured":"Mulmuley, K.: Computational Geometry: An Introduction Through Randomized Algorithms. Englewood Cliffs, Prentice-Hall (1994)"},{"key":"9346_CR31","first-page":"390","volume-title":"Proc. 15th Annu. ACM Sympos. Comput. Geom. (SoCG)","author":"E.A. Ramos","year":"1999","unstructured":"Ramos, E.A.: On range reporting, ray shooting and k-level construction. In: Proc. 15th Annu. ACM Sympos. Comput. Geom. (SoCG), pp. 390\u2013399 (1999)"},{"key":"9346_CR32","unstructured":"Seidel, R.: A method for proving lower bounds for certain geometric problems. Tech. Rep. TR84-592, Cornell University, Ithaca, NY, USA (1984)"},{"issue":"1","key":"9346_CR33","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0925-7721(91)90012-4","volume":"1","author":"R. Seidel","year":"1991","unstructured":"Seidel, R.: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Comput. Geom. Theory Appl. 1(1), 51\u201364 (1991)","journal-title":"Comput. Geom. Theory Appl."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-011-9346-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-011-9346-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-011-9346-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,9]],"date-time":"2019-06-09T11:54:18Z","timestamp":1560081258000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-011-9346-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3,25]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,6]]}},"alternative-id":["9346"],"URL":"https:\/\/doi.org\/10.1007\/s00454-011-9346-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3,25]]}}}