[{"keyword":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"article_processing_charge":"No","arxiv":1,"fulldoi":"https://doi.org/10.1145/3446383","publication_status":"published","title":"Exploiting spontaneous transmissions for broadcasting and leader election in radio networks","type":"journal_article","status":"public","intvolume":"        68","article_type":"original","publication_identifier":{"eissn":["1557-735X"],"issn":["0004-5411"]},"volume":68,"quality_controlled":"1","issue":"2","article_number":"13","department":[{"_id":"DaAl"}],"_id":"15267","publisher":"ACM","month":"01","oa_version":"Preprint","external_id":{"arxiv":["1703.01859"]},"abstract":[{"text":"We study two fundamental communication primitives: broadcasting and leader election in the classical model of multi-hop radio networks with unknown topology and without collision detection mechanisms. It has been known for almost 20 years that in undirected networks with n nodes and diameter D, randomized broadcasting requires Ω(D log n/D + log2 n) rounds, assuming that uninformed nodes are not allowed to communicate (until they are informed). Only very recently, Haeupler and Wajc (PODC'2016) showed that this bound can be improved for the model with spontaneous transmissions, providing an O(D log n log log n/log D + logO(1) n)-time broadcasting algorithm. In this article, we give a new and faster algorithm that completes broadcasting in O(D log n/log D + logO(1) n) time, succeeding with high probability. This yields the first optimal O(D)-time broadcasting algorithm whenever n is polynomial in D.\r\n\r\nFurthermore, our approach can be applied to design a new leader election algorithm that matches the performance of our broadcasting algorithm. Previously, all fast randomized leader election algorithms have used broadcasting as a subroutine and their complexity has been asymptotically strictly larger than the complexity of broadcasting. In particular, the fastest previously known randomized leader election algorithm of Ghaffari and Haeupler (SODA'2013) requires O(D log n/D min {log log n, log n/D} + logO(1) n)-time, succeeding with high probability. Our new algorithm again requires O(D log n/log D + logO(1) n) time, also succeeding with high probability.","lang":"eng"}],"date_published":"2021-01-28T00:00:00Z","day":"28","doi":"10.1145/3446383","citation":{"chicago":"Czumaj, Artur, and Peter Davies. “Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks.” <i>Journal of the ACM</i>. ACM, 2021. <a href=\"https://doi.org/10.1145/3446383\">https://doi.org/10.1145/3446383</a>.","mla":"Czumaj, Artur, and Peter Davies. “Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks.” <i>Journal of the ACM</i>, vol. 68, no. 2, 13, ACM, 2021, doi:<a href=\"https://doi.org/10.1145/3446383\">10.1145/3446383</a>.","ieee":"A. Czumaj and P. Davies, “Exploiting spontaneous transmissions for broadcasting and leader election in radio networks,” <i>Journal of the ACM</i>, vol. 68, no. 2. ACM, 2021.","short":"A. Czumaj, P. Davies, Journal of the ACM 68 (2021).","ama":"Czumaj A, Davies P. Exploiting spontaneous transmissions for broadcasting and leader election in radio networks. <i>Journal of the ACM</i>. 2021;68(2). doi:<a href=\"https://doi.org/10.1145/3446383\">10.1145/3446383</a>","ista":"Czumaj A, Davies P. 2021. Exploiting spontaneous transmissions for broadcasting and leader election in radio networks. Journal of the ACM. 68(2), 13.","apa":"Czumaj, A., &#38; Davies, P. (2021). Exploiting spontaneous transmissions for broadcasting and leader election in radio networks. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/3446383\">https://doi.org/10.1145/3446383</a>"},"year":"2021","date_created":"2024-04-03T07:41:46Z","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1703.01859","open_access":"1"}],"publication":"Journal of the ACM","author":[{"first_name":"Artur","last_name":"Czumaj","full_name":"Czumaj, Artur"},{"orcid":"0000-0002-5646-9524","full_name":"Davies, Peter","last_name":"Davies","first_name":"Peter","id":"11396234-BB50-11E9-B24C-90FCE5697425"}],"date_updated":"2026-08-12T14:03:54Z"},{"publisher":"ACM","oa_version":"Preprint","month":"07","external_id":{"isi":["000487714900008"],"arxiv":["1705.01433"]},"department":[{"_id":"ToHe"}],"_id":"6752","quality_controlled":"1","issue":"4","article_number":"31","intvolume":"        66","publication_identifier":{"issn":["0004-5411"],"eissn":["1557-735X"]},"volume":66,"author":[{"orcid":"0000-0001-5588-8287","full_name":"Avni, Guy","last_name":"Avni","id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","first_name":"Guy"},{"last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","orcid":"0000−0002−2985−7724","full_name":"Henzinger, Thomas A"},{"last_name":"Chonev","first_name":"Ventsislav K","id":"36CBE2E6-F248-11E8-B48F-1D18A9856A87","full_name":"Chonev, Ventsislav K"}],"date_updated":"2025-07-10T11:53:47Z","citation":{"mla":"Avni, Guy, et al. “Infinite-Duration Bidding Games.” <i>Journal of the ACM</i>, vol. 66, no. 4, 31, ACM, 2019, doi:<a href=\"https://doi.org/10.1145/3340295\">10.1145/3340295</a>.","short":"G. Avni, T.A. Henzinger, V.K. Chonev, Journal of the ACM 66 (2019).","ieee":"G. Avni, T. A. Henzinger, and V. K. Chonev, “Infinite-duration bidding games,” <i>Journal of the ACM</i>, vol. 66, no. 4. ACM, 2019.","chicago":"Avni, Guy, Thomas A Henzinger, and Ventsislav K Chonev. “Infinite-Duration Bidding Games.” <i>Journal of the ACM</i>. ACM, 2019. <a href=\"https://doi.org/10.1145/3340295\">https://doi.org/10.1145/3340295</a>.","apa":"Avni, G., Henzinger, T. A., &#38; Chonev, V. K. (2019). Infinite-duration bidding games. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/3340295\">https://doi.org/10.1145/3340295</a>","ama":"Avni G, Henzinger TA, Chonev VK. Infinite-duration bidding games. <i>Journal of the ACM</i>. 2019;66(4). doi:<a href=\"https://doi.org/10.1145/3340295\">10.1145/3340295</a>","ista":"Avni G, Henzinger TA, Chonev VK. 2019. Infinite-duration bidding games. Journal of the ACM. 66(4), 31."},"year":"2019","date_created":"2019-08-04T21:59:16Z","publication":"Journal of the ACM","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1705.01433"}],"abstract":[{"text":"Two-player games on graphs are widely studied in formal methods, as they model the interaction between a system and its environment. The game is played by moving a token throughout a graph to produce an infinite path. There are several common modes to determine how the players move the token through the graph; e.g., in turn-based games the players alternate turns in moving the token. We study the bidding mode of moving the token, which, to the best of our knowledge, has never been studied in infinite-duration games. The following bidding rule was previously defined and called Richman bidding. Both players have separate budgets, which sum up to 1. In each turn, a bidding takes place: Both players submit bids simultaneously, where a bid is legal if it does not exceed the available budget, and the higher bidder pays his bid to the other player and moves the token. The central question studied in bidding games is a necessary and sufficient initial budget for winning the game: a threshold budget in a vertex is a value t ∈ [0, 1] such that if Player 1’s budget exceeds t, he can win the game; and if Player 2’s budget exceeds 1 − t, he can win the game. Threshold budgets were previously shown to exist in every vertex of a reachability game, which have an interesting connection with random-turn games—a sub-class of simple stochastic games in which the player who moves is chosen randomly. We show the existence of threshold budgets for a qualitative class of infinite-duration games, namely parity games, and a quantitative class, namely mean-payoff games. The key component of the proof is a quantitative solution to strongly connected mean-payoff bidding games in which we extend the connection with random-turn games to these games, and construct explicit optimal strategies for both players.","lang":"eng"}],"scopus_import":"1","day":"16","date_published":"2019-07-16T00:00:00Z","doi":"10.1145/3340295","related_material":{"record":[{"id":"950","status":"public","relation":"earlier_version"}]},"oa":1,"article_processing_charge":"No","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","type":"journal_article","publication_status":"published","project":[{"_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211","name":"Formal methods for the design and analysis of complex systems","call_identifier":"FWF"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S11402-N23","_id":"25F2ACDE-B435-11E9-9278-68D0E5697425"},{"name":"Formal Methods meets Algorithmic Game Theory","grant_number":"M02369","_id":"264B3912-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"title":"Infinite-duration bidding games","isi":1,"arxiv":1,"fulldoi":"https://doi.org/10.1145/3340295"},{"scopus_import":"1","abstract":[{"lang":"eng","text":"In the decremental single-source shortest paths (SSSP) problem, we want to maintain the distances between a given source node s and every other node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach [16] has been the fastest known algorithm for three decades. At the cost of a (1+ϵ)-approximation factor, the running time was recently improved to n2+o(1) by Bernstein and Roditty [9]. In this article, we bring the running time down to near-linear: We give a (1+ϵ)-approximation algorithm with m1+o(1) expected total update time, thus obtaining near-linear time. Moreover, we obtain m1+o(1) log W time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(mn) time is the mn0.9 + o(1)-time algorithm by Henzinger et al. [18, 19], which works for directed graphs with quasi-polynomial edge weights. The expected running time bound of our algorithm holds against an oblivious adversary.\r\n\r\nIn contrast to the previous results, which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (h, ϵ)-hop set introduced by Cohen [12] in the PRAM literature. An (h, ϵ)-hop set of a graph G=(V, E) is a set F of weighted edges such that the distance between any pair of nodes in G can be (1+ϵ)-approximated by their h-hop distance (given by a path containing at most h edges) on G′=(V, E ∪ F). Our algorithm can maintain an (no(1), ϵ)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain approximate distances using this hop set, we extend the monotone Even-Shiloach tree of Henzinger et al. [20] and combine it with the bounded-hop SSSP technique of Bernstein [4, 5] and Mądry [27]. These two new tools might be of independent interest."}],"doi":"10.1145/3218657","day":"01","date_published":"2018-12-01T00:00:00Z","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"first_name":"Sebastian","last_name":"Krinninger","full_name":"Krinninger, Sebastian"},{"full_name":"Nanongkai, Danupon","first_name":"Danupon","last_name":"Nanongkai"}],"date_updated":"2024-11-06T12:18:17Z","date_created":"2022-08-08T12:33:17Z","year":"2018","citation":{"ieee":"M. Henzinger, S. Krinninger, and D. Nanongkai, “Decremental single-source shortest paths on undirected graphs in near-linear total update time,” <i>Journal of the ACM</i>, vol. 65, no. 6. Association for Computing Machinery, pp. 1–40, 2018.","short":"M. Henzinger, S. Krinninger, D. Nanongkai, Journal of the ACM 65 (2018) 1–40.","mla":"Henzinger, Monika, et al. “Decremental Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update Time.” <i>Journal of the ACM</i>, vol. 65, no. 6, Association for Computing Machinery, 2018, pp. 1–40, doi:<a href=\"https://doi.org/10.1145/3218657\">10.1145/3218657</a>.","chicago":"Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “Decremental Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update Time.” <i>Journal of the ACM</i>. Association for Computing Machinery, 2018. <a href=\"https://doi.org/10.1145/3218657\">https://doi.org/10.1145/3218657</a>.","apa":"Henzinger, M., Krinninger, S., &#38; Nanongkai, D. (2018). Decremental single-source shortest paths on undirected graphs in near-linear total update time. <i>Journal of the ACM</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3218657\">https://doi.org/10.1145/3218657</a>","ama":"Henzinger M, Krinninger S, Nanongkai D. Decremental single-source shortest paths on undirected graphs in near-linear total update time. <i>Journal of the ACM</i>. 2018;65(6):1-40. doi:<a href=\"https://doi.org/10.1145/3218657\">10.1145/3218657</a>","ista":"Henzinger M, Krinninger S, Nanongkai D. 2018. Decremental single-source shortest paths on undirected graphs in near-linear total update time. Journal of the ACM. 65(6), 1–40."},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1512.08148"}],"publication":"Journal of the ACM","quality_controlled":"1","extern":"1","issue":"6","intvolume":"        65","volume":65,"publication_identifier":{"issn":["0004-5411"],"eissn":["1557-735X"]},"article_type":"original","oa_version":"Preprint","month":"12","publisher":"Association for Computing Machinery","external_id":{"arxiv":["1512.08148"]},"_id":"11768","title":"Decremental single-source shortest paths on undirected graphs in near-linear total update time","publication_status":"published","fulldoi":"https://doi.org/10.1145/3218657","arxiv":1,"status":"public","type":"journal_article","oa":1,"related_material":{"record":[{"id":"11855","status":"public","relation":"earlier_version"}]},"article_processing_charge":"No","page":"1-40","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}]},{"date_updated":"2026-08-26T11:21:19Z","author":[{"full_name":"Ban, Yih","first_name":"Yih","last_name":"Ban"},{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner"},{"full_name":"Rudolph, Johannes","first_name":"Johannes","last_name":"Rudolph"}],"publication":"Journal of the ACM","year":"2006","date_created":"2018-12-11T12:06:14Z","citation":{"apa":"Ban, Y., Edelsbrunner, H., &#38; Rudolph, J. (2006). Interface surfaces for protein-protein complexes. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/1147954.1147957\">https://doi.org/10.1145/1147954.1147957</a>","ista":"Ban Y, Edelsbrunner H, Rudolph J. 2006. Interface surfaces for protein-protein complexes. Journal of the ACM. 53(3), 361–378.","ama":"Ban Y, Edelsbrunner H, Rudolph J. Interface surfaces for protein-protein complexes. <i>Journal of the ACM</i>. 2006;53(3):361-378. doi:<a href=\"https://doi.org/10.1145/1147954.1147957\">10.1145/1147954.1147957</a>","short":"Y. Ban, H. Edelsbrunner, J. Rudolph, Journal of the ACM 53 (2006) 361–378.","ieee":"Y. Ban, H. Edelsbrunner, and J. Rudolph, “Interface surfaces for protein-protein complexes,” <i>Journal of the ACM</i>, vol. 53, no. 3. ACM, pp. 361–378, 2006.","mla":"Ban, Yih, et al. “Interface Surfaces for Protein-Protein Complexes.” <i>Journal of the ACM</i>, vol. 53, no. 3, ACM, 2006, pp. 361–78, doi:<a href=\"https://doi.org/10.1145/1147954.1147957\">10.1145/1147954.1147957</a>.","chicago":"Ban, Yih, Herbert Edelsbrunner, and Johannes Rudolph. “Interface Surfaces for Protein-Protein Complexes.” <i>Journal of the ACM</i>. ACM, 2006. <a href=\"https://doi.org/10.1145/1147954.1147957\">https://doi.org/10.1145/1147954.1147957</a>."},"doi":"10.1145/1147954.1147957","date_published":"2006-05-01T00:00:00Z","day":"01","abstract":[{"text":"Protein-protein interactions, which form the basis for most cellular processes, result in the formation of protein interfaces. Believing that the local shape of proteins is crucial, we take a geometric approach and present a definition of an interface surface formed by two or more proteins as a subset of their Voronoi diagram. The definition deals with the difficult and important problem of specifying interface boundaries by invoking methods used in the alpha shape representation of molecules, the discrete flow on Delaunay simplices to define pockets and reconstruct surfaces, and the assessment of the importance of topological features. We present an algorithm to construct the surface and define a hierarchy that distinguishes core and peripheral regions. This hierarchy is shown to have correlation with hot-spots in protein-protein interactions. Finally, we study the geometric and topological properties of interface surfaces and show their high degree of contortion.","lang":"eng"}],"oa_version":"None","month":"05","publisher":"ACM","_id":"3979","extern":"1","issue":"3","volume":53,"article_type":"original","publication_identifier":{"issn":["0004-5411"],"eissn":["1557-735X"]},"intvolume":"        53","status":"public","OA_type":"closed access","type":"journal_article","title":"Interface surfaces for protein-protein complexes","publication_status":"published","fulldoi":"https://doi.org/10.1145/1147954.1147957","publist_id":"2147","article_processing_charge":"No","page":"361 - 378","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","language":[{"iso":"eng"}]},{"_id":"11769","oa_version":"None","month":"07","publisher":"Association for Computing Machinery","volume":46,"publication_identifier":{"eissn":["1557-735X"],"issn":["0004-5411"]},"article_type":"original","intvolume":"        46","extern":"1","issue":"4","quality_controlled":"1","publication":"Journal of the ACM","year":"1999","date_created":"2022-08-08T12:50:25Z","citation":{"ieee":"M. Henzinger and V. King, “Randomized fully dynamic graph algorithms with polylogarithmic time per operation,” <i>Journal of the ACM</i>, vol. 46, no. 4. Association for Computing Machinery, pp. 502–516, 1999.","short":"M. Henzinger, V. King, Journal of the ACM 46 (1999) 502–516.","mla":"Henzinger, Monika, and Valerie King. “Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation.” <i>Journal of the ACM</i>, vol. 46, no. 4, Association for Computing Machinery, 1999, pp. 502–16, doi:<a href=\"https://doi.org/10.1145/320211.320215\">10.1145/320211.320215</a>.","chicago":"Henzinger, Monika, and Valerie King. “Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation.” <i>Journal of the ACM</i>. Association for Computing Machinery, 1999. <a href=\"https://doi.org/10.1145/320211.320215\">https://doi.org/10.1145/320211.320215</a>.","apa":"Henzinger, M., &#38; King, V. (1999). Randomized fully dynamic graph algorithms with polylogarithmic time per operation. <i>Journal of the ACM</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/320211.320215\">https://doi.org/10.1145/320211.320215</a>","ama":"Henzinger M, King V. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. <i>Journal of the ACM</i>. 1999;46(4):502-516. doi:<a href=\"https://doi.org/10.1145/320211.320215\">10.1145/320211.320215</a>","ista":"Henzinger M, King V. 1999. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. Journal of the ACM. 46(4), 502–516."},"date_updated":"2024-11-06T08:15:30Z","author":[{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"last_name":"King","first_name":"Valerie","full_name":"King, Valerie"}],"doi":"10.1145/320211.320215","day":"01","date_published":"1999-07-01T00:00:00Z","abstract":[{"text":"This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion or deletion. The algorithms are designed using a new dynamic technique that combines a novel graph decomposition with randomization. They are Las-Vegas type randomized algorithms which use simple data structures and have a small constant factor.\r\nLet n denote the number of nodes in the graph. For a sequence of Ω(m0) operations, where m0 is the number of edges in the initial graph, the expected time for p updates is O(p log3 n) (througout the paper the logarithms are based 2) for connectivity and bipartiteness. The worst-case time for one query is O(log n/log log n). For the k-edge witness problem (“Does the removal of k given edges disconnect the graph?”) the expected time for p updates is O(p log3 n) and the expected time for q queries is O(qk log3 n). Given a graph with k different weights, the minimum spanning tree can be maintained during a sequence of p updates in expected time O(pk log3 n). This implies an algorithm to maintain a 1 + ε-approximation of the minimum spanning tree in expected time O((p log3 n logU)/ε) for p updates, where the weights of the edges are between 1 and U.","lang":"eng"}],"scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"502-516","language":[{"iso":"eng"}],"article_processing_charge":"No","type":"journal_article","status":"public","fulldoi":"https://doi.org/10.1145/320211.320215","title":"Randomized fully dynamic graph algorithms with polylogarithmic time per operation","publication_status":"published"},{"doi":"10.1145/147508.147511","day":"01","date_published":"1992-01-01T00:00:00Z","abstract":[{"text":"The main contribution of this work is an O(n log n + k)-time algorithm for computing all k intersections among n line segments in the plane. This time complexity is easily shown to be optimal. Within the same asymptotic cost, our algorithm can also construct the subdivision of the plane defined by the segments and compute which segment (if any) lies right above (or below) each intersection and each endpoint. The algorithm has been implemented and performs very well. The storage requirement is on the order of n + k in the worst case, but it is considerably lower in practice. To analyze the complexity of the algorithm, an amortization argument based on a new combinatorial theorem on line arrangements is used.","lang":"eng"}],"scopus_import":"1","date_updated":"2022-03-16T08:32:17Z","author":[{"full_name":"Chazelle, Bernard","first_name":"Bernard","last_name":"Chazelle"},{"last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert"}],"publication":"Journal of the ACM","main_file_link":[{"url":"https://dl.acm.org/doi/10.1145/147508.147511"}],"date_created":"2018-12-11T12:06:37Z","year":"1992","citation":{"chicago":"Chazelle, Bernard, and Herbert Edelsbrunner. “An Optimal Algorithm for Intersecting Line Segments in the Plane.” <i>Journal of the ACM</i>. ACM, 1992. <a href=\"https://doi.org/10.1145/147508.147511\">https://doi.org/10.1145/147508.147511</a>.","mla":"Chazelle, Bernard, and Herbert Edelsbrunner. “An Optimal Algorithm for Intersecting Line Segments in the Plane.” <i>Journal of the ACM</i>, vol. 39, no. 1, ACM, 1992, pp. 1–54, doi:<a href=\"https://doi.org/10.1145/147508.147511\">10.1145/147508.147511</a>.","short":"B. Chazelle, H. Edelsbrunner, Journal of the ACM 39 (1992) 1–54.","ieee":"B. Chazelle and H. Edelsbrunner, “An optimal algorithm for intersecting line segments in the plane,” <i>Journal of the ACM</i>, vol. 39, no. 1. ACM, pp. 1–54, 1992.","ista":"Chazelle B, Edelsbrunner H. 1992. An optimal algorithm for intersecting line segments in the plane. Journal of the ACM. 39(1), 1–54.","ama":"Chazelle B, Edelsbrunner H. An optimal algorithm for intersecting line segments in the plane. <i>Journal of the ACM</i>. 1992;39(1):1-54. doi:<a href=\"https://doi.org/10.1145/147508.147511\">10.1145/147508.147511</a>","apa":"Chazelle, B., &#38; Edelsbrunner, H. (1992). An optimal algorithm for intersecting line segments in the plane. <i>Journal of the ACM</i>. ACM. <a href=\"https://doi.org/10.1145/147508.147511\">https://doi.org/10.1145/147508.147511</a>"},"extern":"1","issue":"1","quality_controlled":"1","volume":39,"publication_identifier":{"issn":["0004-5411"],"eissn":["1557-735X"]},"article_type":"original","intvolume":"        39","month":"01","oa_version":"None","publisher":"ACM","_id":"4046","acknowledgement":"B, Chazelle wishes to acknowledge the National Science Foundation for supporting this research in part under Grant CCR 87-00917. H, Edelsbrunner is pleased to acknowledge the support of Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and the NSF under Grant CCR 87-14565. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for\r\nComputing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission.","title":"An optimal algorithm for intersecting line segments in the plane","publication_status":"published","fulldoi":"https://doi.org/10.1145/147508.147511","publist_id":"2078","status":"public","type":"journal_article","article_processing_charge":"No","page":"1 - 54","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","language":[{"iso":"eng"}]}]