{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:27:26Z","timestamp":1760441246540},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,12,4]],"date-time":"2014-12-04T00:00:00Z","timestamp":1417651200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00453-014-9950-0","type":"journal-article","created":{"date-parts":[[2014,12,3]],"date-time":"2014-12-03T10:19:56Z","timestamp":1417601996000},"page":"415-439","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["The Higher-Order Voronoi Diagram of Line Segments"],"prefix":"10.1007","volume":"74","author":[{"given":"Evanthia","family":"Papadopoulou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maksym","family":"Zavershynskyi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,12,4]]},"reference":[{"issue":"3","key":"9950_CR1","doi-asserted-by":"crossref","first-page":"654","DOI":"10.1137\/S0097539795281840","volume":"27","author":"PK Agarwal","year":"1998","unstructured":"Agarwal, P.K., de Berg, M., Matousek, J., Schwarzkopf, O.: Constructing levels in arrangements and higher-order Voronoi diagrams. SIAM J. Comput. 27(3), 654\u2013667 (1998)","journal-title":"SIAM J. Comput."},{"key":"9950_CR2","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.B., Shor, P.W.: A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete Comput. Geom. 4, 591\u2013604 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"9950_CR3","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1142\/S0218195992000214","volume":"2","author":"F Aurenhammer","year":"1992","unstructured":"Aurenhammer, F., Schwarzkopf, O.: A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams. Int. J. Comput. Geom. Appl. 2(4), 363\u2013381 (1992)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"6","key":"9950_CR4","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/j.ipl.2006.07.008","volume":"100","author":"F Aurenhammer","year":"2006","unstructured":"Aurenhammer, F., Drysdale, R.L.S., Krasser, H.: Farthest line segment Voronoi diagrams. Inf. Process. Lett. 100(6), 220\u2013225 (2006)","journal-title":"Inf. Process. Lett."},{"key":"9950_CR5","unstructured":"Aurenhammer, F., Klein, K., Lee, D.-T.: Voronoi Diagrams and Delaunay Triangulations, World Scientific, 1\u2013337, ISBN 978-981-4447-63-8, pp. I-VIII (2013)"},{"key":"9950_CR6","first-page":"208","volume-title":"ICALP 2013. Lecture Notes in Computer Science","author":"C Bohler","year":"2013","unstructured":"Bohler, C., Klein, R., Liu, C.-H., Papadopoulou, E., Cheilaris, P., Zavershynskyi, M.: On the complexity of higher order abstract Voronoi diagrams. In: Fomin, F.V., et al. (eds.) ICALP 2013. Lecture Notes in Computer Science, vol. 7965, pp. 208\u2013219. Springer, Heidelberg (2013)"},{"key":"9950_CR7","doi-asserted-by":"crossref","unstructured":"Bohler, C., Liu, C.-H., Papadopoulou, E., Zavershynskyi, M.: A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams. 25th International Symposium on Algorithms and Computation, ISAAC 2014. Lecture Notes in Computer Science, vol. 8889, (to appear)","DOI":"10.1007\/978-3-319-13075-0_3"},{"issue":"2","key":"9950_CR8","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1137\/S0097539798349188","volume":"30","author":"TM Chan","year":"2000","unstructured":"Chan, T.M.: Random sampling, halfspace range reporting, and construction of $$\\le k$$ \u2264 k -levels in three dimensions. SIAM J. Comput. 30(2), 561\u2013575 (2000)","journal-title":"SIAM J. Comput."},{"issue":"11","key":"9950_CR9","doi-asserted-by":"crossref","first-page":"1349","DOI":"10.1109\/TC.1987.5009474","volume":"36","author":"B Chazelle","year":"1987","unstructured":"Chazelle, B., Edelsbrunner, H.: An improved algorithm for constructing kth-order Voronoi diagrams. IEEE Trans. Comput. 36(11), 1349\u20131454 (1987)","journal-title":"IEEE Trans. Comput."},{"issue":"4","key":"9950_CR10","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1016\/j.comgeo.2010.11.004","volume":"44","author":"O Cheong","year":"2011","unstructured":"Cheong, O., Everett, H., Glisse, M., Gudmundsson, J., Hornus, S., Lazard, S., Lee, M., Na, H.-S.: Farthest-polygon Voronoi diagrams. Comput. Geom. 44(4), 234\u2013247 (2011)","journal-title":"Comput. Geom."},{"key":"9950_CR11","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"KL Clarkson","year":"1987","unstructured":"Clarkson, K.L.: New applications of random sampling in computational geometry. Discrete Comput. Geom. 2, 195\u2013222 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"9950_CR12","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"KL Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Application of random sampling in computational geometry, II. Discrete Comput. Geom. 4, 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"9950_CR13","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H.: The complexity of higher-order Voronoi diagrams. In: Edelsbrunner, H.: Algorithms in Combinatorial Geometry, pp. 319\u2013324. EATCS monographs on theoretical computer science. Springer, Nre York (1987)","DOI":"10.1007\/978-3-642-61568-9_13"},{"issue":"3","key":"9950_CR14","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1007\/BF01934440","volume":"22","author":"H Edelsbrunner","year":"1982","unstructured":"Edelsbrunner, H., Maurer, H.A., Preparata, F.P., Rosenberg, A.L., Welzl, E., Wood, D.: Stabbing line segments. BIT 22(3), 274\u2013281 (1982)","journal-title":"BIT"},{"key":"9950_CR15","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D.G.: Efficient computation of continuous skeletons. FOCS: 18\u201327, 20th Annual Symposium on Foundations of Computer Science (1979)","DOI":"10.1109\/SFCS.1979.15"},{"issue":"9","key":"9950_CR16","doi-asserted-by":"crossref","first-page":"885","DOI":"10.1016\/j.comgeo.2009.03.002","volume":"42","author":"R Klein","year":"2009","unstructured":"Klein, R., Langetepe, E., Nilforoushan, Z.: Abstract Voronoi diagrams revisited. Comput. Geom. 42(9), 885\u2013902 (2009)","journal-title":"Comput. Geom."},{"issue":"4","key":"9950_CR17","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1145\/322217.322219","volume":"27","author":"DT Lee","year":"1980","unstructured":"Lee, D.T.: Two-dimensional Voronoi diagrams in the $$\\text{ L }_{p}$$ L p -metric. J. ACM 27(4), 604\u2013618 (1980)","journal-title":"J. ACM"},{"issue":"6","key":"9950_CR18","first-page":"478","volume":"31","author":"DT Lee","year":"1982","unstructured":"Lee, D.T.: On k-nearest neighbor Voronoi diagrams in the plane. IEEE Trans. Comput. 31(6), 478\u2013487 (1982)","journal-title":"IEEE Trans. Comput."},{"key":"9950_CR19","doi-asserted-by":"crossref","unstructured":"Liu, C.-H., Papadopoulou, E., Lee, D.T.: The k-nearest-neighbor Voronoi diagram revisited. Algorithmica (2013). doi: 10.1007\/s00453-013-9809-9","DOI":"10.1007\/s00453-013-9809-9"},{"issue":"6","key":"9950_CR20","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1142\/S0218195901000663","volume":"11","author":"K Mehlhorn","year":"2001","unstructured":"Mehlhorn, K., Meiser, S., Rasch, R.: Furthest site abstract Voronoi diagrams. Int. J. Comput. Geom. Appl. 11(6), 583\u2013616 (2001)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"5","key":"9950_CR21","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1109\/TCAD.2010.2100550","volume":"30","author":"E Papadopoulou","year":"2011","unstructured":"Papadopoulou, E.: Net-aware critical area extraction for opens in VLSI circuits via higher-order Voronoi diagrams. IEEE Trans. CAD Integr. Circuits Syst. 30(5), 704\u2013717 (2011)","journal-title":"IEEE Trans. CAD Integr. Circuits Syst."},{"issue":"6","key":"9950_CR22","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1142\/S0218195913600121","volume":"23","author":"E Papadopoulou","year":"2013","unstructured":"Papadopoulou, E., Dey, S.K.: On the farthest line segment Voronoi diagram. Int. J. Comput. Geom. Appl. 23(6), 443\u2013460 (2013)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9950_CR23","doi-asserted-by":"crossref","unstructured":"Papadopoulou, E., Zavershynskyi, M.Z.: On higher order Voronoi diagrams of line segments. In: Chao, K.-M. et al. (eds.) ISAAC 2012, Lecture Notes in Computer Science, 7676, 177\u2013186 (2012)","DOI":"10.1007\/978-3-642-35261-4_21"},{"key":"9950_CR24","doi-asserted-by":"crossref","unstructured":"Ramos, E.A.: On range reporting, ray shooting and k-level construction. In: Proceedings of 15th Annual Symposium on Computational Geometry, 390\u2013399 (1999)","DOI":"10.1145\/304893.304993"},{"key":"9950_CR25","first-page":"57","volume-title":"WADS 1989. Lecture Notes in Computer Science","author":"D Rappaport","year":"1989","unstructured":"Rappaport, D.: Computing the furthest site Voronoi diagram for a set of discs (preliminary report). In: Dehne, F.K.H.A., et al. (eds.) WADS 1989. Lecture Notes in Computer Science, vol. 382, pp. 57\u201366. Springer, Heidelberg (1989)"},{"issue":"4","key":"9950_CR26","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1007\/BF01759056","volume":"6","author":"H Rosenberger","year":"1991","unstructured":"Rosenberger, H.: Order-k Voronoi diagrams of sites with additive weights in the plane. Algorithmica 6(4), 490\u2013521 (1991)","journal-title":"Algorithmica"},{"issue":"1","key":"9950_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00009330","volume":"19","author":"R Seidel","year":"1998","unstructured":"Seidel, R.: The nature and meaning of perturbations in geometric computing. Discrete Comput. Geom. 19(1), 1\u201317 (1998)","journal-title":"Discrete Comput. Geom."},{"key":"9950_CR28","volume-title":"Davenport-Schinzel Sequences and Their Geometric Applications","author":"M Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge (1995)"},{"issue":"2","key":"9950_CR29","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1017\/S0963548302005527","volume":"12","author":"M Sharir","year":"2003","unstructured":"Sharir, M.: The Clarkson\u2013Shor technique revisited and extended. Comb. Probab. Comput. 12(2), 191\u2013201 (2003)","journal-title":"Comb. Probab. Comput."},{"key":"9950_CR30","doi-asserted-by":"crossref","unstructured":"Zavershynskyi, M., Papadopoulou, E.: A sweepline algorithm for higher order Voronoi diagrams. In: Proceedings of 10th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2013. IEEE-CS, pp. 16\u201322 (2013)","DOI":"10.1109\/ISVD.2013.17"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9950-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9950-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9950-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,17]],"date-time":"2019-08-17T23:31:52Z","timestamp":1566084712000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9950-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,4]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9950"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9950-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,4]]}}}