{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T02:01:46Z","timestamp":1780538506245,"version":"3.54.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1986,11,1]],"date-time":"1986-11-01T00:00:00Z","timestamp":531187200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1986,11]]},"DOI":"10.1007\/bf01840438","type":"journal-article","created":{"date-parts":[[2005,7,13]],"date-time":"2005-07-13T21:29:13Z","timestamp":1121290153000},"page":"93-109","source":"Crossref","is-referenced-by-count":30,"title":["Edge-skeletons in arrangements with applications"],"prefix":"10.1007","volume":"1","author":[{"given":"H.","family":"Edelsbrunner","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF01840438_CR1","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The design and analysis of computer algorithms. Addison Wesley, 1974."},{"key":"BF01840438_CR2","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1080\/0025570X.1978.11976715","volume":"51","author":"G. L. Alexanderson","year":"1978","unstructured":"G. L. Alexanderson and J. E. Wetzel, Simple partitions of space.Math. Mag. 51 (1978), 220\u2013225.","journal-title":"Math. Mag."},{"key":"BF01840438_CR3","unstructured":"F. Aurenhammer, Power diagrams: properties, algorithms, and applications. Rep. F 120, Inst. Inform. Process., Techn. Univ. Graz, Austria, 1983."},{"key":"BF01840438_CR4","unstructured":"B. M. Chazelle and F. P. Preparata, Halfspatial range search: an algorithmic application ofk-sets. To appear inJ. Discrete Comput. Geom."},{"key":"BF01840438_CR5","doi-asserted-by":"crossref","unstructured":"R. Cole, M. Sharir and C. K. Yap, Onk-hulls and related problems.Proc. 16th Ann. ACM Symp. Theor. Comput. Sci. (1984), 154\u2013166.","DOI":"10.1145\/800057.808677"},{"key":"BF01840438_CR6","doi-asserted-by":"crossref","unstructured":"D. P. Dobkin and H. Edelsbrunner, Space searching for intersecting objects.Proc. 25th Ann. IEEE Symp. Found. Comput. Sci. (1984), 387\u2013392.","DOI":"10.1109\/SFCS.1984.715939"},{"key":"BF01840438_CR7","unstructured":"H. Edelsbrunner and F. Huber, Dissecting sets of points in two and three dimensions. Rep. F 138, Inst. Inform. Process., Techn. Univ. Graz, Austria, 1984."},{"key":"BF01840438_CR8","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0020-0190(85)90107-3","volume":"21","author":"H. Edelsbrunner","year":"1985","unstructured":"H. Edelsbrunner and H. A. Maurer, Finding extreme points in three dimensions and solving the post-office problem in the plane.Inform. Process. Lett. 21 (1985), 39\u201347.","journal-title":"Inform. Process. Lett."},{"key":"BF01840438_CR9","doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner, J. O'Rourke and R. Seidel, Constructing arrangements of lines and hyperplanes with applications.Proc. 24th Ann. IEEE Symp. Found. Comput. Sci. (1983), 83\u201391.","DOI":"10.1109\/SFCS.1983.11"},{"key":"BF01840438_CR10","doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner and R. Seidel, Voronoi diagrams and arrangements.Proc. Sympos. Comput. Geom., Baltimore (1985), 251\u2013262.","DOI":"10.1145\/323233.323266"},{"key":"BF01840438_CR11","unstructured":"H. Edelsbrunner and G. Stoeckl, The number of extreme pairs of finite point-sets in Euclidean spaces. Rep. F 142, Inst. Inform. Process., Techn. Univ. Graz, Austria, 1984."},{"key":"BF01840438_CR12","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0097-3165(85)90017-2","volume":"38","author":"H. Edelsbrunner","year":"1985","unstructured":"H. Edelsbrunner and E. Welzl, On the number of line separations of a finite set in the plane.J. Combin. Theory Ser. A 38 (1985), 15\u201329.","journal-title":"J. Combin. Theory Ser. A"},{"key":"BF01840438_CR13","doi-asserted-by":"crossref","unstructured":"P. Erdoes, L. Lovasz, A. Simmons and E. G. Straus, Dissection graphs of planar point-sets. In:A survey of combinatorial theory, J. N. Srivastava et al. (eds.), North Holland, 1973, 139\u2013149.","DOI":"10.1016\/B978-0-7204-2262-7.50018-1"},{"key":"BF01840438_CR14","unstructured":"I. G. Gowda and D. G. Kirkpatrick, Exploiting linear merging and extra storage in the maintenance of fully dynamic geometric data structures.Proc. 18th Ann. Allerton Conf. Commun., Contr., Comput. (1980), 1\u201310."},{"key":"BF01840438_CR15","unstructured":"B. Gruenbaum, Arrangements and hyperplanes.Congr. Number. III,Louis. Conf. Combin.,Graph Th., Comput. (1971), 41\u2013106."},{"key":"BF01840438_CR16","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1137\/0214006","volume":"14","author":"H. Imai","year":"1985","unstructured":"H. Imai, M. Iri and K. Murota, Voronoi diagram in the Laguerre metric and its applications.SIAM J. Comput. 14 (1985), 93\u2013105.","journal-title":"SIAM J. Comput."},{"key":"BF01840438_CR17","unstructured":"D. E. Knuth,Searching and sorting. The art of computer programming III. Addison-Wesley, 1973."},{"key":"BF01840438_CR18","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1109\/TC.1982.1676031","volume":"C-31","author":"D. T. Lee","year":"1982","unstructured":"D. T. Lee, Onk-nearest neighbour Voronoi diagram in the plane.IEEE Trans. Comput. C-31 (1982), 478\u2013487.","journal-title":"IEEE Trans. Comput."},{"key":"BF01840438_CR19","unstructured":"H. A. Maurer and Th. Ottmann, Dynamic solutions of decomposable searching problems. In:Discrete structures and algorithms, U. Pape, (ed.), Carl Hanser (1979), 17\u201324."},{"key":"BF01840438_CR20","unstructured":"N. Megiddo, Partitioning with two lines in the plane. To appear inJ. Algorithms."},{"key":"BF01840438_CR21","doi-asserted-by":"crossref","unstructured":"F. P. Preparata and S. J. Hong, Convex hulls of finite sets of points in two and three dimensions.Comm. ACM (1977), 87\u201393.","DOI":"10.1145\/359423.359430"},{"key":"BF01840438_CR22","doi-asserted-by":"crossref","unstructured":"M. I. Shamos and D. Hoey, Closest-point problems.Proc. 16th Ann. IEEE Symp. Found. Comput. Sci. (1975), 151\u2013162.","DOI":"10.1109\/SFCS.1975.8"},{"key":"BF01840438_CR23","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/S0020-0190(80)90073-3","volume":"10","author":"J. Leeuwen van","year":"1980","unstructured":"J. van Leeuwen and D. Wood, Dynamization of decomposable searching problems.Inform. Process. Lett. 10 (1980), 51\u201356.","journal-title":"Inform. Process. Lett."},{"key":"BF01840438_CR24","unstructured":"F. F. Yao, D. P. Dobkin and H. Edelsbrunner, Manuscript, 1985."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840438.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01840438\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840438","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T06:59:16Z","timestamp":1586329156000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01840438"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,11]]},"references-count":24,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1986,11]]}},"alternative-id":["BF01840438"],"URL":"https:\/\/doi.org\/10.1007\/bf01840438","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,11]]}}}