[{"ec_funded":1,"author":[{"full_name":"Krokhin, Andrei","first_name":"Andrei","last_name":"Krokhin"},{"full_name":"Opršal, Jakub","last_name":"Opršal","first_name":"Jakub","orcid":"0000-0003-1245-3456","id":"ec596741-c539-11ec-b829-c79322a91242"},{"last_name":"Wrochna","first_name":"Marcin","full_name":"Wrochna, Marcin"},{"full_name":"Živný, Stanislav","first_name":"Stanislav","last_name":"Živný"}],"date_created":"2023-02-16T07:03:52Z","date_updated":"2023-08-01T13:11:30Z","volume":52,"year":"2023","acknowledgement":"Andrei Krokhin and Jakub Opršal were supported by the UK EPSRC grant EP/R034516/1. Jakub Opršal has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413. Stanislav Živný was supported by a Royal Society University Research Fellowship. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 714532). The paper re\u001eects only the authors’ views and not the views of the ERC or the European Commission. ","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Society for Industrial & Applied Mathematics","month":"01","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"doi":"10.1137/20m1378223","language":[{"iso":"eng"}],"external_id":{"isi":["000955000000001"],"arxiv":["2003.11351"]},"oa":1,"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2003.11351","open_access":"1"}],"quality_controlled":"1","isi":1,"project":[{"call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"abstract":[{"text":"he approximate graph coloring problem, whose complexity is unresolved in most cases, concerns finding a c-coloring of a graph that is promised to be k-colorable, where c≥k. This problem naturally generalizes to promise graph homomorphism problems and further to promise constraint satisfaction problems. The complexity of these problems has recently been studied through an algebraic approach. In this paper, we introduce two new techniques to analyze the complexity of promise CSPs: one is based on topology and the other on adjunction. We apply these techniques, together with the previously introduced algebraic approach, to obtain new unconditional NP-hardness results for a significant class of approximate graph coloring and promise graph homomorphism problems.","lang":"eng"}],"issue":"1","type":"journal_article","oa_version":"Preprint","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"12563","title":"Topology and adjunction in promise constraint satisfaction","status":"public","intvolume":" 52","day":"01","article_processing_charge":"No","scopus_import":"1","keyword":["General Mathematics","General Computer Science"],"date_published":"2023-01-01T00:00:00Z","publication":"SIAM Journal on Computing","citation":{"ista":"Krokhin A, Opršal J, Wrochna M, Živný S. 2023. Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing. 52(1), 38–79.","ieee":"A. Krokhin, J. Opršal, M. Wrochna, and S. Živný, “Topology and adjunction in promise constraint satisfaction,” SIAM Journal on Computing, vol. 52, no. 1. Society for Industrial & Applied Mathematics, pp. 38–79, 2023.","apa":"Krokhin, A., Opršal, J., Wrochna, M., & Živný, S. (2023). Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/20m1378223","ama":"Krokhin A, Opršal J, Wrochna M, Živný S. Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing. 2023;52(1):38-79. doi:10.1137/20m1378223","chicago":"Krokhin, Andrei, Jakub Opršal, Marcin Wrochna, and Stanislav Živný. “Topology and Adjunction in Promise Constraint Satisfaction.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2023. https://doi.org/10.1137/20m1378223.","mla":"Krokhin, Andrei, et al. “Topology and Adjunction in Promise Constraint Satisfaction.” SIAM Journal on Computing, vol. 52, no. 1, Society for Industrial & Applied Mathematics, 2023, pp. 38–79, doi:10.1137/20m1378223.","short":"A. Krokhin, J. Opršal, M. Wrochna, S. Živný, SIAM Journal on Computing 52 (2023) 38–79."},"article_type":"original","page":"38-79"},{"acknowledgement":"The authors have received funding from the European Research Council under the European Union's ERC grant greement 339025 GUDHI (Algorithmic Foundations of Geometric Un-derstanding in Higher Dimensions). The first author was supported by the French government,through the 3IA C\\^ote d'Azur Investments in the Future project managed by the National ResearchAgency (ANR) with the reference ANR-19-P3IA-0002. The third author was supported by the Eu-ropean Union's Horizon 2020 research and innovation programme under the Marie Sk\\lodowska-Curiegrant agreement 754411 and the FWF (Austrian Science Fund) grant M 3073.","year":"2023","publisher":"Society for Industrial and Applied Mathematics","department":[{"_id":"HeEd"}],"publication_status":"published","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"9441"}]},"author":[{"last_name":"Boissonnat","first_name":"Jean Daniel","full_name":"Boissonnat, Jean Daniel"},{"full_name":"Kachanovich, Siargey","last_name":"Kachanovich","first_name":"Siargey"},{"full_name":"Wintraecken, Mathijs","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","first_name":"Mathijs","last_name":"Wintraecken"}],"volume":52,"date_created":"2023-05-14T22:01:00Z","date_updated":"2023-10-10T07:34:35Z","ec_funded":1,"main_file_link":[{"open_access":"1","url":"https://hal-emse.ccsd.cnrs.fr/3IA-COTEDAZUR/hal-04083489v1"}],"external_id":{"isi":["001013183000012"]},"oa":1,"project":[{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships"},{"_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","grant_number":"M03073","name":"Learning and triangulating manifolds via collapses"}],"isi":1,"quality_controlled":"1","doi":"10.1137/21M1412918","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"month":"04","_id":"12960","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 52","title":"Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations","status":"public","oa_version":"Submitted Version","type":"journal_article","issue":"2","abstract":[{"text":"Isomanifolds are the generalization of isosurfaces to arbitrary dimension and codimension, i.e., submanifolds of Rd defined as the zero set of some multivariate multivalued smooth function f:Rd→Rd−n, where n is the intrinsic dimension of the manifold. A natural way to approximate a smooth isomanifold M=f−1(0) is to consider its piecewise linear (PL) approximation M^\r\n based on a triangulation T of the ambient space Rd. In this paper, we describe a simple algorithm to trace isomanifolds from a given starting point. The algorithm works for arbitrary dimensions n and d, and any precision D. Our main result is that, when f (or M) has bounded complexity, the complexity of the algorithm is polynomial in d and δ=1/D (and unavoidably exponential in n). Since it is known that for δ=Ω(d2.5), M^ is O(D2)-close and isotopic to M\r\n, our algorithm produces a faithful PL-approximation of isomanifolds of bounded complexity in time polynomial in d. Combining this algorithm with dimensionality reduction techniques, the dependency on d in the size of M^ can be completely removed with high probability. We also show that the algorithm can handle isomanifolds with boundary and, more generally, isostratifolds. The algorithm for isomanifolds with boundary has been implemented and experimental results are reported, showing that it is practical and can handle cases that are far ahead of the state-of-the-art. ","lang":"eng"}],"citation":{"chicago":"Boissonnat, Jean Daniel, Siargey Kachanovich, and Mathijs Wintraecken. “Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter–Freudenthal–Kuhn Triangulations.” SIAM Journal on Computing. Society for Industrial and Applied Mathematics, 2023. https://doi.org/10.1137/21M1412918.","mla":"Boissonnat, Jean Daniel, et al. “Tracing Isomanifolds in Rd in Time Polynomial in d Using Coxeter–Freudenthal–Kuhn Triangulations.” SIAM Journal on Computing, vol. 52, no. 2, Society for Industrial and Applied Mathematics, 2023, pp. 452–86, doi:10.1137/21M1412918.","short":"J.D. Boissonnat, S. Kachanovich, M. Wintraecken, SIAM Journal on Computing 52 (2023) 452–486.","ista":"Boissonnat JD, Kachanovich S, Wintraecken M. 2023. Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations. SIAM Journal on Computing. 52(2), 452–486.","ieee":"J. D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations,” SIAM Journal on Computing, vol. 52, no. 2. Society for Industrial and Applied Mathematics, pp. 452–486, 2023.","apa":"Boissonnat, J. D., Kachanovich, S., & Wintraecken, M. (2023). Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations. SIAM Journal on Computing. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/21M1412918","ama":"Boissonnat JD, Kachanovich S, Wintraecken M. Tracing isomanifolds in Rd in time polynomial in d using Coxeter–Freudenthal–Kuhn triangulations. SIAM Journal on Computing. 2023;52(2):452-486. doi:10.1137/21M1412918"},"publication":"SIAM Journal on Computing","page":"452-486","article_type":"original","date_published":"2023-04-30T00:00:00Z","scopus_import":"1","article_processing_charge":"No","day":"30"},{"issue":"5","abstract":[{"lang":"eng","text":"n the dynamic minimum set cover problem, the challenge is to minimize the update time while guaranteeing a close-to-optimal min{O(log n), f} approximation factor. (Throughout, n, m, f , and C are parameters denoting the maximum number of elements, the number of sets, the frequency, and the cost range.) In the high-frequency range, when f = Ω(log n) , this was achieved by a deterministic O(log n) -approximation algorithm with O(f log n) amortized update time by Gupta et al. [Online and dynamic algorithms for set cover, in Proceedings STOC 2017, ACM, pp. 537–550]. In this paper we consider the low-frequency range, when f = O(log n) , and obtain deterministic algorithms with a (1 + ∈)f -approximation ratio and the following guarantees on the update time. (1) O ((f/∈)-log(Cn)) amortized update time: Prior to our work, the best approximation ratio guaranteed by deterministic algorithms was O(f2) of Bhattacharya, Henzinger, and Italiano [Design of dynamic algorithms via primal-dual method, in Proceedings ICALP 2015, Springer, pp. 206–218]. In contrast, the only result with O(f) -approximation was that of Abboud et al. [Dynamic set cover: Improved algorithms and lower bounds, in Proceedings STOC 2019, ACM, pp. 114–125], who designed a randomized (1+∈)f -approximation algorithm with amortized update time. (2) O(f2/∈3 + (f/∈2).logC) amortized update time: This result improves the above update time bound for most values of f\r\n in the low-frequency range, i.e., f=o(log n) . It is also the first result that is independent of m\r\n and n. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [Deterministically maintaining a (2 + ∈) -approximate minimum vertex cover in O(1/∈2) amortized update time, in Proceedings SODA 2019, SIAM, pp. 1872–1885] for unweighted dynamic vertex cover (i.e., when f = 2 and C = 1). (3) O((f/∈3).log2(Cn)) worst-case update time: No nontrivial worst-case update time was previously known for the dynamic set cover problem. Our bound subsumes and improves by a logarithmic factor the O(log3n/poly (∈)) \r\n worst-case update time for the unweighted dynamic vertex cover problem (i.e., when f = 2\r\n and C =1) of Bhattacharya, Henzinger, and Nanongkai [Fully dynamic approximate maximum matching and minimum vertex cover in O(log3)n worst case update time, in Proceedings SODA 2017, SIAM, pp. 470–489]. We achieve our results via the primal-dual approach, by maintaining a fractional packing solution as a dual certificate. Prior work in dynamic algorithms that employs the primal-dual approach uses a local update scheme that maintains relaxed complementary slackness conditions for every set. For our first result we use instead a global update scheme that does not always maintain complementary slackness conditions. For our second result we combine the global and the local update schema. To achieve our third result we use a hierarchy of background schedulers. It is an interesting open question whether this background scheduler technique can also be used to transform algorithms with amortized running time bounds into algorithms with worst-case running time bounds."}],"type":"journal_article","oa_version":"None","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"14558","intvolume":" 52","status":"public","title":"Deterministic near-optimal approximation algorithms for dynamic set cover","article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"2023-10-01T00:00:00Z","citation":{"short":"S. Bhattacharya, M.H. Henzinger, D. Nanongkai, X. Wu, SIAM Journal on Computing 52 (2023) 1132–1192.","mla":"Bhattacharya, Sayan, et al. “Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover.” SIAM Journal on Computing, vol. 52, no. 5, Society for Industrial and Applied Mathematics, 2023, pp. 1132–92, doi:10.1137/21M1428649.","chicago":"Bhattacharya, Sayan, Monika H Henzinger, Danupon Nanongkai, and Xiaowei Wu. “Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover.” SIAM Journal on Computing. Society for Industrial and Applied Mathematics, 2023. https://doi.org/10.1137/21M1428649.","ama":"Bhattacharya S, Henzinger MH, Nanongkai D, Wu X. Deterministic near-optimal approximation algorithms for dynamic set cover. SIAM Journal on Computing. 2023;52(5):1132-1192. doi:10.1137/21M1428649","ieee":"S. Bhattacharya, M. H. Henzinger, D. Nanongkai, and X. Wu, “Deterministic near-optimal approximation algorithms for dynamic set cover,” SIAM Journal on Computing, vol. 52, no. 5. Society for Industrial and Applied Mathematics, pp. 1132–1192, 2023.","apa":"Bhattacharya, S., Henzinger, M. H., Nanongkai, D., & Wu, X. (2023). Deterministic near-optimal approximation algorithms for dynamic set cover. SIAM Journal on Computing. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/21M1428649","ista":"Bhattacharya S, Henzinger MH, Nanongkai D, Wu X. 2023. Deterministic near-optimal approximation algorithms for dynamic set cover. SIAM Journal on Computing. 52(5), 1132–1192."},"publication":"SIAM Journal on Computing","page":"1132-1192","article_type":"original","ec_funded":1,"author":[{"full_name":"Bhattacharya, Sayan","last_name":"Bhattacharya","first_name":"Sayan"},{"last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"},{"first_name":"Danupon","last_name":"Nanongkai","full_name":"Nanongkai, Danupon"},{"last_name":"Wu","first_name":"Xiaowei","full_name":"Wu, Xiaowei"}],"volume":52,"date_created":"2023-11-19T23:00:56Z","date_updated":"2023-11-20T08:21:07Z","year":"2023","acknowledgement":"This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grants 715672 and\r\n101019564 ``The Design of Modern Fully Dynamic Data Structures (MoDynStruct)\"\") and from the Engineering and Physical Sciences Research Council, UK (EPSRC) under grant EP/S03353X/1. The second author was also supported by the Austrian Science Fund (FWF) project ``Fast Algorithms for a Reactive Network Layer (ReactNet),\"\" P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020--2024, project ``Static and Dynamic Hierarchical Graph Decompositions,\"\"I 5982-N, and project Z 422-N. The third author was also supported by the Swedish Research Council (Reg. No. 2015-04659). The fourth author was also supported by the Science and Technology Development Fund (FDCT), Macau SAR (file 0014/2022/AFJ, 0085/2022/A, 0143/2020/A3, and SKL-IOTSC-2021-2023).","publisher":"Society for Industrial and Applied Mathematics","department":[{"_id":"MoHe"}],"publication_status":"published","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"month":"10","doi":"10.1137/21M1428649","language":[{"iso":"eng"}],"project":[{"call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775 "},{"grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Wittgenstein Award - Monika Henzinger"},{"grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions"}],"quality_controlled":"1"},{"issue":"4","abstract":[{"text":"We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve -set agreement among processes or approximate agreement on a cycle of length 4 among processes in a wait-free manner in asynchronous models where processes communicate using objects that can be constructed from shared registers. However, it was unknown whether proofs based on simpler techniques were possible. We show that these impossibility results cannot be obtained by extension-based proofs in the iterated snapshot model and, hence, extension-based proofs are limited in power.","lang":"eng"}],"type":"journal_article","oa_version":"Preprint","_id":"14364","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 52","title":"Why extension-based proofs fail","status":"public","article_processing_charge":"No","day":"25","scopus_import":"1","date_published":"2023-07-25T00:00:00Z","citation":{"mla":"Alistarh, Dan-Adrian, et al. “Why Extension-Based Proofs Fail.” SIAM Journal on Computing, vol. 52, no. 4, Society for Industrial and Applied Mathematics, 2023, pp. 913–44, doi:10.1137/20M1375851.","short":"D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, SIAM Journal on Computing 52 (2023) 913–944.","chicago":"Alistarh, Dan-Adrian, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu. “Why Extension-Based Proofs Fail.” SIAM Journal on Computing. Society for Industrial and Applied Mathematics, 2023. https://doi.org/10.1137/20M1375851.","ama":"Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. Why extension-based proofs fail. SIAM Journal on Computing. 2023;52(4):913-944. doi:10.1137/20M1375851","ista":"Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. 2023. Why extension-based proofs fail. SIAM Journal on Computing. 52(4), 913–944.","apa":"Alistarh, D.-A., Aspnes, J., Ellen, F., Gelashvili, R., & Zhu, L. (2023). Why extension-based proofs fail. SIAM Journal on Computing. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/20M1375851","ieee":"D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, and L. Zhu, “Why extension-based proofs fail,” SIAM Journal on Computing, vol. 52, no. 4. Society for Industrial and Applied Mathematics, pp. 913–944, 2023."},"publication":"SIAM Journal on Computing","page":"913-944","article_type":"original","ec_funded":1,"related_material":{"record":[{"id":"6676","status":"public","relation":"earlier_version"}]},"author":[{"full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X"},{"last_name":"Aspnes","first_name":"James","full_name":"Aspnes, James"},{"last_name":"Ellen","first_name":"Faith","full_name":"Ellen, Faith"},{"first_name":"Rati","last_name":"Gelashvili","full_name":"Gelashvili, Rati"},{"id":"a2117c59-cee4-11ed-b9d0-874ecf0f8ac5","first_name":"Leqi","last_name":"Zhu","full_name":"Zhu, Leqi"}],"volume":52,"date_created":"2023-09-24T22:01:11Z","date_updated":"2023-12-13T12:28:29Z","acknowledgement":"We would like to thank Valerie King, Toniann Pitassi, and Michael Saks for helpful discussions and Shi Hao Liu for his useful feedback.\r\nThis research was supported by the Natural Science and Engineering Research Council of Canada under grants RGPIN-2015-05080 and RGPIN-2020-04178, a postgraduate scholarship, and a postdoctoral fellowship; a University of Toronto postdoctoral fellowship; the National Science Foundation under grants CCF-1217921, CCF-1301926, CCF-1637385, CCF-1650596, and IIS-1447786; the U.S. Department of Energy under grant ER26116/DE-SC0008923; the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme grant agreement 805223 ScaleML; and the Oracle and Intel corporations. Some of the work on this paper was done while Faith Ellen was visiting IST Austria.","year":"2023","department":[{"_id":"DaAl"}],"publisher":"Society for Industrial and Applied Mathematics","publication_status":"published","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"month":"07","doi":"10.1137/20M1375851","language":[{"iso":"eng"}],"external_id":{"isi":["001082972300004"],"arxiv":["1811.01421"]},"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1811.01421"}],"project":[{"grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning"}],"isi":1,"quality_controlled":"1"},{"article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"2021-05-01T00:00:00Z","citation":{"ama":"Henzinger MH, Krinninger S, Nanongkai D. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. SIAM Journal on Computing. 2021;50(3):STOC16-98-STOC16-137. doi:10.1137/16m1097808","apa":"Henzinger, M. H., Krinninger, S., & Nanongkai, D. (2021). A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/16m1097808","ieee":"M. H. Henzinger, S. Krinninger, and D. Nanongkai, “A deterministic almost-tight distributed algorithm for approximating single-source shortest paths,” SIAM Journal on Computing, vol. 50, no. 3. Society for Industrial & Applied Mathematics, pp. STOC16-98-STOC16-137, 2021.","ista":"Henzinger MH, Krinninger S, Nanongkai D. 2021. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. SIAM Journal on Computing. 50(3), STOC16-98-STOC16-137.","short":"M.H. Henzinger, S. Krinninger, D. Nanongkai, SIAM Journal on Computing 50 (2021) STOC16-98-STOC16-137.","mla":"Henzinger, Monika H., et al. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.” SIAM Journal on Computing, vol. 50, no. 3, Society for Industrial & Applied Mathematics, 2021, pp. STOC16-98-STOC16-137, doi:10.1137/16m1097808.","chicago":"Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2021. https://doi.org/10.1137/16m1097808."},"publication":"SIAM Journal on Computing","page":"STOC16-98-STOC16-137","article_type":"original","issue":"3","abstract":[{"text":"We present a deterministic (1+𝑜(1))-approximation (𝑛1/2+𝑜(1)+𝐷1+𝑜(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the \\sf CONGEST model); here 𝑛 is the number of nodes in the network, 𝐷 is its (hop) diameter, and edge weights are positive integers from 1 to poly(𝑛). This is the first nontrivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+𝑜(1))-approximation 𝑂̃ (𝑛√𝐷1/4+𝐷)-time algorithm of Nanongkai [in Proceedings of STOC, 2014, pp. 565--573] by a factor of as large as 𝑛1/8, and (ii) the 𝑂(𝜖−1log𝜖−1)-approximation factor of Lenzen and Patt-Shamir's 𝑂̃ (𝑛1/2+𝜖+𝐷)-time algorithm [in Proceedings of STOC, 2013, pp. 381--390] within the same running time. (Throughout, we use 𝑂̃ (⋅) to hide polylogarithmic factors in 𝑛.) Our running time matches the known time lower bound of Ω(𝑛/log𝑛‾‾‾‾‾‾‾√+𝐷) [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433--456], thus essentially settling the status of this problem which was raised at least a decade ago [M. Elkin, SIGACT News, 35 (2004), pp. 40--57]. It also implies a (2+𝑜(1))-approximation (𝑛1/2+𝑜(1)+𝐷1+𝑜(1))-time algorithm for approximating a network's weighted diameter which almost matches the lower bound by Holzer and Pinsker [in Proceedings of OPODIS, 2015, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2016, 6]. In achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the “hitting set argument” commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic construction of an (𝑛𝑜(1),𝑜(1))-hop set of size 𝑛1+𝑜(1). We combine these techniques with many distributed algorithmic techniques, some of which are from problems that are not directly related to shortest paths, e.g., ruling sets [A. V. Goldberg, S. A. Plotkin, and G. E. Shannon, SIAM J. Discrete Math., 1 (1988), pp. 434--446], source detection [C. Lenzen and D. Peleg, in Proceedings of PODC, 2013, pp. 375--382], and partial distance estimation [C. Lenzen and B. Patt-Shamir, in Proceedings of PODC, 2015, pp. 153--162]. Our hop set construction also leads to single-source shortest paths algorithms in two other settings: (i) a (1+𝑜(1))-approximation 𝑛𝑜(1)-time algorithm on congested cliques, and (ii) a (1+𝑜(1))-approximation 𝑛𝑜(1)-pass 𝑛1+𝑜(1)-space streaming algorithm. The first result answers an open problem in [D. Nanongkai, in Proceedings of STOC, 2014, pp. 565--573]. The second result partially answers an open problem raised by McGregor in 2006 [List of Open Problems in Sublinear Algorithms: Problem 14].","lang":"eng"}],"type":"journal_article","oa_version":"Preprint","_id":"11886","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 50","title":"A deterministic almost-tight distributed algorithm for approximating single-source shortest paths","status":"public","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"month":"05","doi":"10.1137/16m1097808","language":[{"iso":"eng"}],"oa":1,"external_id":{"arxiv":["1504.07056"]},"main_file_link":[{"url":"https://arxiv.org/abs/1504.07056","open_access":"1"}],"quality_controlled":"1","extern":"1","author":[{"full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"full_name":"Krinninger, Sebastian","first_name":"Sebastian","last_name":"Krinninger"},{"full_name":"Nanongkai, Danupon","last_name":"Nanongkai","first_name":"Danupon"}],"volume":50,"date_updated":"2023-02-17T14:12:49Z","date_created":"2022-08-17T07:54:45Z","year":"2021","publisher":"Society for Industrial & Applied Mathematics","publication_status":"published"},{"author":[{"full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"full_name":"Rao, Satish","last_name":"Rao","first_name":"Satish"},{"first_name":"Di","last_name":"Wang","full_name":"Wang, Di"}],"related_material":{"record":[{"status":"public","relation":"later_version","id":"11873"}]},"date_updated":"2023-02-21T16:31:25Z","date_created":"2022-08-17T08:09:31Z","volume":49,"year":"2020","publication_status":"published","publisher":"Society for Industrial & Applied Mathematics","extern":"1","doi":"10.1137/18m1180335","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://arxiv.org/abs/1704.01254"}],"external_id":{"arxiv":["1704.01254"]},"quality_controlled":"1","month":"01","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11889","title":"Local flow partitioning for faster edge connectivity","status":"public","intvolume":" 49","abstract":[{"text":"We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic 𝑂(𝑚log2𝑛loglog2𝑛) time algorithm. This improves on both the best previously known deterministic running time of 𝑂(𝑚log12𝑛) (Kawarabayashi and Thorup [J. ACM, 66 (2018), 4]) and the best previously known randomized running time of 𝑂(𝑚log3𝑛) (Karger [J. ACM, 47 (2000), pp. 46--76]) for this problem, though Karger's algorithm can be further applied to weighted graphs. Moreover, our result extends to balanced directed graphs, where the balance of a directed graph captures how close the graph is to being Eulerian. Our approach is using the Kawarabayashi and Thorup graph compression technique, which repeatedly finds low conductance cuts. To find these cuts they use a diffusion-based local algorithm. We use instead a flow-based local algorithm and suitably adjust their framework to work with our flow-based subroutine. Both flow- and diffusion-based methods have a long history of being applied to finding low conductance cuts. Diffusion algorithms have several variants that are naturally local, while it is more complicated to make flow methods local. Some prior work has proven nice properties for local flow-based algorithms with respect to improving or cleaning up low conductance cuts. Our flow subroutine, however, is the first that both is local and produces low conductance cuts. Thus, it may be of independent interest.","lang":"eng"}],"issue":"1","type":"journal_article","date_published":"2020-01-01T00:00:00Z","publication":"SIAM Journal on Computing","citation":{"chicago":"Henzinger, Monika H, Satish Rao, and Di Wang. “Local Flow Partitioning for Faster Edge Connectivity.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2020. https://doi.org/10.1137/18m1180335.","mla":"Henzinger, Monika H., et al. “Local Flow Partitioning for Faster Edge Connectivity.” SIAM Journal on Computing, vol. 49, no. 1, Society for Industrial & Applied Mathematics, 2020, pp. 1–36, doi:10.1137/18m1180335.","short":"M.H. Henzinger, S. Rao, D. Wang, SIAM Journal on Computing 49 (2020) 1–36.","ista":"Henzinger MH, Rao S, Wang D. 2020. Local flow partitioning for faster edge connectivity. SIAM Journal on Computing. 49(1), 1–36.","apa":"Henzinger, M. H., Rao, S., & Wang, D. (2020). Local flow partitioning for faster edge connectivity. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/18m1180335","ieee":"M. H. Henzinger, S. Rao, and D. Wang, “Local flow partitioning for faster edge connectivity,” SIAM Journal on Computing, vol. 49, no. 1. Society for Industrial & Applied Mathematics, pp. 1–36, 2020.","ama":"Henzinger MH, Rao S, Wang D. Local flow partitioning for faster edge connectivity. SIAM Journal on Computing. 2020;49(1):1-36. doi:10.1137/18m1180335"},"article_type":"original","page":"1-36","day":"01","article_processing_charge":"No","scopus_import":"1"},{"type":"journal_article","abstract":[{"lang":"eng","text":"The construction of anisotropic triangulations is desirable for various applications, such as the numerical solving of partial differential equations and the representation of surfaces in graphics. To solve this notoriously difficult problem in a practical way, we introduce the discrete Riemannian Voronoi diagram, a discrete structure that approximates the Riemannian Voronoi diagram. This structure has been implemented and was shown to lead to good triangulations in $\\mathbb{R}^2$ and on surfaces embedded in $\\mathbb{R}^3$ as detailed in our experimental companion paper. In this paper, we study theoretical aspects of our structure. Given a finite set of points $\\mathcal{P}$ in a domain $\\Omega$ equipped with a Riemannian metric, we compare the discrete Riemannian Voronoi diagram of $\\mathcal{P}$ to its Riemannian Voronoi diagram. Both diagrams have dual structures called the discrete Riemannian Delaunay and the Riemannian Delaunay complex. We provide conditions that guarantee that these dual structures are identical. It then follows from previous results that the discrete Riemannian Delaunay complex can be embedded in $\\Omega$ under sufficient conditions, leading to an anisotropic triangulation with curved simplices. Furthermore, we show that, under similar conditions, the simplices of this triangulation can be straightened."}],"issue":"3","extern":"1","year":"2019","_id":"6672","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","title":"Anisotropic triangulations via discrete Riemannian Voronoi diagrams","publication_status":"published","publisher":"Society for Industrial & Applied Mathematics (SIAM)","intvolume":" 48","author":[{"first_name":"Jean-Daniel","last_name":"Boissonnat","full_name":"Boissonnat, Jean-Daniel"},{"last_name":"Rouxel-Labbé","first_name":"Mael","full_name":"Rouxel-Labbé, Mael"},{"full_name":"Wintraecken, Mathijs","orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","last_name":"Wintraecken","first_name":"Mathijs"}],"date_created":"2019-07-24T08:42:12Z","date_updated":"2021-01-12T08:08:30Z","oa_version":"Preprint","volume":48,"month":"05","day":"21","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"publication":"SIAM Journal on Computing","main_file_link":[{"url":"https://arxiv.org/abs/1703.06487","open_access":"1"}],"citation":{"short":"J.-D. Boissonnat, M. Rouxel-Labbé, M. Wintraecken, SIAM Journal on Computing 48 (2019) 1046–1097.","mla":"Boissonnat, Jean-Daniel, et al. “Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams.” SIAM Journal on Computing, vol. 48, no. 3, Society for Industrial & Applied Mathematics (SIAM), 2019, pp. 1046–97, doi:10.1137/17m1152292.","chicago":"Boissonnat, Jean-Daniel, Mael Rouxel-Labbé, and Mathijs Wintraecken. “Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM), 2019. https://doi.org/10.1137/17m1152292.","ama":"Boissonnat J-D, Rouxel-Labbé M, Wintraecken M. Anisotropic triangulations via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. 2019;48(3):1046-1097. doi:10.1137/17m1152292","ieee":"J.-D. Boissonnat, M. Rouxel-Labbé, and M. Wintraecken, “Anisotropic triangulations via discrete Riemannian Voronoi diagrams,” SIAM Journal on Computing, vol. 48, no. 3. Society for Industrial & Applied Mathematics (SIAM), pp. 1046–1097, 2019.","apa":"Boissonnat, J.-D., Rouxel-Labbé, M., & Wintraecken, M. (2019). Anisotropic triangulations via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM). https://doi.org/10.1137/17m1152292","ista":"Boissonnat J-D, Rouxel-Labbé M, Wintraecken M. 2019. Anisotropic triangulations via discrete Riemannian Voronoi diagrams. SIAM Journal on Computing. 48(3), 1046–1097."},"oa":1,"external_id":{"arxiv":["1703.06487"]},"quality_controlled":"1","page":"1046-1097","date_published":"2019-05-21T00:00:00Z","doi":"10.1137/17m1152292","language":[{"iso":"eng"}]},{"ec_funded":1,"department":[{"_id":"VlKo"}],"publisher":"SIAM","publication_status":"published","year":"2019","volume":48,"date_created":"2020-01-30T09:27:32Z","date_updated":"2023-09-06T15:25:29Z","author":[{"last_name":"Achlioptas","first_name":"Dimitris","full_name":"Achlioptas, Dimitris"},{"last_name":"Iliopoulos","first_name":"Fotis","full_name":"Iliopoulos, Fotis"},{"last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir"}],"publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"month":"10","project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","call_identifier":"FP7"}],"isi":1,"quality_controlled":"1","oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1809.01537"}],"external_id":{"arxiv":["1809.01537"],"isi":["000493900200005"]},"language":[{"iso":"eng"}],"doi":"10.1137/16m109332x","type":"journal_article","issue":"5","abstract":[{"text":"We develop a framework for the rigorous analysis of focused stochastic local search algorithms. These algorithms search a state space by repeatedly selecting some constraint that is violated in the current state and moving to a random nearby state that addresses the violation, while (we hope) not introducing many new violations. An important class of focused local search algorithms with provable performance guarantees has recently arisen from algorithmizations of the Lovász local lemma (LLL), a nonconstructive tool for proving the existence of satisfying states by introducing a background measure on the state space. While powerful, the state transitions of algorithms in this class must be, in a precise sense, perfectly compatible with the background measure. In many applications this is a very restrictive requirement, and one needs to step outside the class. Here we introduce the notion of measure distortion and develop a framework for analyzing arbitrary focused stochastic local search algorithms, recovering LLL algorithmizations as the special case of no distortion. Our framework takes as input an arbitrary algorithm of such type and an arbitrary probability measure and shows how to use the measure as a yardstick of algorithmic progress, even for algorithms designed independently of the measure.","lang":"eng"}],"intvolume":" 48","status":"public","title":"A local lemma for focused stochastical algorithms","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"7412","oa_version":"Preprint","scopus_import":"1","article_processing_charge":"No","day":"31","page":"1583-1602","article_type":"original","citation":{"ieee":"D. Achlioptas, F. Iliopoulos, and V. Kolmogorov, “A local lemma for focused stochastical algorithms,” SIAM Journal on Computing, vol. 48, no. 5. SIAM, pp. 1583–1602, 2019.","apa":"Achlioptas, D., Iliopoulos, F., & Kolmogorov, V. (2019). A local lemma for focused stochastical algorithms. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/16m109332x","ista":"Achlioptas D, Iliopoulos F, Kolmogorov V. 2019. A local lemma for focused stochastical algorithms. SIAM Journal on Computing. 48(5), 1583–1602.","ama":"Achlioptas D, Iliopoulos F, Kolmogorov V. A local lemma for focused stochastical algorithms. SIAM Journal on Computing. 2019;48(5):1583-1602. doi:10.1137/16m109332x","chicago":"Achlioptas, Dimitris, Fotis Iliopoulos, and Vladimir Kolmogorov. “A Local Lemma for Focused Stochastical Algorithms.” SIAM Journal on Computing. SIAM, 2019. https://doi.org/10.1137/16m109332x.","short":"D. Achlioptas, F. Iliopoulos, V. Kolmogorov, SIAM Journal on Computing 48 (2019) 1583–1602.","mla":"Achlioptas, Dimitris, et al. “A Local Lemma for Focused Stochastical Algorithms.” SIAM Journal on Computing, vol. 48, no. 5, SIAM, 2019, pp. 1583–602, doi:10.1137/16m109332x."},"publication":"SIAM Journal on Computing","date_published":"2019-10-31T00:00:00Z"},{"oa_version":"Preprint","_id":"11890","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 47","title":"Deterministic fully dynamic data structures for vertex cover and matching","status":"public","issue":"3","abstract":[{"lang":"eng","text":"We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph 𝐺=(𝑉,𝐸), with |𝑉|=𝑛 and |𝐸|=𝑚, in 𝑜(𝑚‾‾√) time per update. In particular, for minimum vertex cover, we provide deterministic data structures for maintaining a (2+𝜖) approximation in 𝑂(log𝑛/𝜖2) amortized time per update. For maximum matching, we show how to maintain a (3+𝜖) approximation in 𝑂(min(𝑛√/𝜖,𝑚1/3/𝜖2) amortized time per update and a (4+𝜖) approximation in 𝑂(𝑚1/3/𝜖2) worst-case time per update. Our data structure for fully dynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld [in 42nd ACM Symposium on Theory of Computing, Cambridge, MA, ACM, 2010, pp. 457--464]."}],"type":"journal_article","date_published":"2018-05-01T00:00:00Z","citation":{"ieee":"S. Bhattacharya, M. H. Henzinger, and G. F. Italiano, “Deterministic fully dynamic data structures for vertex cover and matching,” SIAM Journal on Computing, vol. 47, no. 3. Society for Industrial & Applied Mathematics, pp. 859–887, 2018.","apa":"Bhattacharya, S., Henzinger, M. H., & Italiano, G. F. (2018). Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/140998925","ista":"Bhattacharya S, Henzinger MH, Italiano GF. 2018. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing. 47(3), 859–887.","ama":"Bhattacharya S, Henzinger MH, Italiano GF. Deterministic fully dynamic data structures for vertex cover and matching. SIAM Journal on Computing. 2018;47(3):859-887. doi:10.1137/140998925","chicago":"Bhattacharya, Sayan, Monika H Henzinger, and Giuseppe F. Italiano. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2018. https://doi.org/10.1137/140998925.","short":"S. Bhattacharya, M.H. Henzinger, G.F. Italiano, SIAM Journal on Computing 47 (2018) 859–887.","mla":"Bhattacharya, Sayan, et al. “Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching.” SIAM Journal on Computing, vol. 47, no. 3, Society for Industrial & Applied Mathematics, 2018, pp. 859–87, doi:10.1137/140998925."},"publication":"SIAM Journal on Computing","page":"859-887","article_type":"original","article_processing_charge":"No","day":"01","scopus_import":"1","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"11875"}]},"author":[{"full_name":"Bhattacharya, Sayan","first_name":"Sayan","last_name":"Bhattacharya"},{"orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H"},{"last_name":"Italiano","first_name":"Giuseppe F.","full_name":"Italiano, Giuseppe F."}],"volume":47,"date_updated":"2023-02-21T16:31:30Z","date_created":"2022-08-17T08:21:23Z","year":"2018","publisher":"Society for Industrial & Applied Mathematics","publication_status":"published","extern":"1","doi":"10.1137/140998925","language":[{"iso":"eng"}],"external_id":{"arxiv":["1412.1318"]},"main_file_link":[{"url":"https://arxiv.org/abs/1412.1318","open_access":"1"}],"oa":1,"quality_controlled":"1","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"month":"05"},{"ec_funded":1,"publication_status":"published","department":[{"_id":"VlKo"}],"publisher":"Society for Industrial & Applied Mathematics (SIAM)","year":"2018","date_updated":"2023-09-19T14:24:58Z","date_created":"2019-02-13T12:59:33Z","volume":47,"author":[{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"id":"1193","relation":"earlier_version","status":"public"}]},"month":"11","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"quality_controlled":"1","isi":1,"project":[{"name":"Discrete Optimization in Computer Vision: Theory and Practice","call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160"}],"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1506.08547"}],"external_id":{"arxiv":["1506.08547"],"isi":["000453785100001"]},"language":[{"iso":"eng"}],"doi":"10.1137/16m1093306","type":"journal_article","abstract":[{"text":"We consider the recent formulation of the algorithmic Lov ́asz Local Lemma [N. Har-vey and J. Vondr ́ak, inProceedings of FOCS, 2015, pp. 1327–1345; D. Achlioptas and F. Iliopoulos,inProceedings of SODA, 2016, pp. 2024–2038; D. Achlioptas, F. Iliopoulos, and V. Kolmogorov,ALocal Lemma for Focused Stochastic Algorithms, arXiv preprint, 2018] for finding objects that avoid“bad features,” or “flaws.” It extends the Moser–Tardos resampling algorithm [R. A. Moser andG. Tardos,J. ACM, 57 (2010), 11] to more general discrete spaces. At each step the method picks aflaw present in the current state and goes to a new state according to some prespecified probabilitydistribution (which depends on the current state and the selected flaw). However, the recent formu-lation is less flexible than the Moser–Tardos method since it requires a specific flaw selection rule,whereas the algorithm of Moser and Tardos allows an arbitrary rule (and thus can potentially beimplemented more efficiently). We formulate a new “commutativity” condition and prove that it issufficient for an arbitrary rule to work. It also enables an efficient parallelization under an additionalassumption. We then show that existing resampling oracles for perfect matchings and permutationsdo satisfy this condition.","lang":"eng"}],"issue":"6","title":"Commutativity in the algorithmic Lovász local lemma","status":"public","intvolume":" 47","_id":"5975","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa_version":"Preprint","scopus_import":"1","day":"08","article_processing_charge":"No","page":"2029-2056","publication":"SIAM Journal on Computing","citation":{"ista":"Kolmogorov V. 2018. Commutativity in the algorithmic Lovász local lemma. SIAM Journal on Computing. 47(6), 2029–2056.","apa":"Kolmogorov, V. (2018). Commutativity in the algorithmic Lovász local lemma. SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM). https://doi.org/10.1137/16m1093306","ieee":"V. Kolmogorov, “Commutativity in the algorithmic Lovász local lemma,” SIAM Journal on Computing, vol. 47, no. 6. Society for Industrial & Applied Mathematics (SIAM), pp. 2029–2056, 2018.","ama":"Kolmogorov V. Commutativity in the algorithmic Lovász local lemma. SIAM Journal on Computing. 2018;47(6):2029-2056. doi:10.1137/16m1093306","chicago":"Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovász Local Lemma.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM), 2018. https://doi.org/10.1137/16m1093306.","mla":"Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovász Local Lemma.” SIAM Journal on Computing, vol. 47, no. 6, Society for Industrial & Applied Mathematics (SIAM), 2018, pp. 2029–56, doi:10.1137/16m1093306.","short":"V. Kolmogorov, SIAM Journal on Computing 47 (2018) 2029–2056."},"date_published":"2018-11-08T00:00:00Z"},{"scopus_import":"1","article_processing_charge":"No","day":"01","page":"947-1006","article_type":"original","citation":{"apa":"Henzinger, M. H., Krinninger, S., & Nanongkai, D. (2016). Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/140957299","ieee":"M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization,” SIAM Journal on Computing, vol. 45, no. 3. Society for Industrial & Applied Mathematics, pp. 947–1006, 2016.","ista":"Henzinger MH, Krinninger S, Nanongkai D. 2016. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. SIAM Journal on Computing. 45(3), 947–1006.","ama":"Henzinger MH, Krinninger S, Nanongkai D. Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization. SIAM Journal on Computing. 2016;45(3):947-1006. doi:10.1137/140957299","chicago":"Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2016. https://doi.org/10.1137/140957299.","short":"M.H. Henzinger, S. Krinninger, D. Nanongkai, SIAM Journal on Computing 45 (2016) 947–1006.","mla":"Henzinger, Monika H., et al. “Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(Mn) Barrier and Derandomization.” SIAM Journal on Computing, vol. 45, no. 3, Society for Industrial & Applied Mathematics, 2016, pp. 947–1006, doi:10.1137/140957299."},"publication":"SIAM Journal on Computing","date_published":"2016-05-01T00:00:00Z","type":"journal_article","issue":"3","abstract":[{"text":"We study dynamic (1+𝜖)-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected 𝑛-node 𝑚-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of 𝑂̃ (𝑚𝑛/𝜖) and constant query time by Roditty and Zwick [SIAM J. Comput., 41 (2012), pp. 670--683]. The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach [J. ACM, 28 (1981), pp. 1--4]; it has a total update time of 𝑂(𝑚𝑛2) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of 𝑂̃ (𝑛5/2/𝜖) and constant query time that has an additive error of 2 in addition to the 1+𝜖 multiplicative error. This beats the previous 𝑂̃ (𝑚𝑛/𝜖) time when 𝑚=Ω(𝑛3/2). Note that the additive error is unavoidable since, even in the static case, an 𝑂(𝑛3−𝛿)-time (a so-called truly subcubic) combinatorial algorithm with 1+𝜖 multiplicative error cannot have an additive error less than 2−𝜖, unless we make a major breakthrough for Boolean matrix multiplication [D. Dor, S. Halrepin, and U. Zwick, SIAM J. Comput., 29 (2000), pp. 1740--1759] and many other long-standing problems [V. Vassilevska Williams and R. Williams, Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 645--654]. The algorithm can also be turned into a (2+𝜖)-approximation algorithm (without an additive error) with the same time guarantees, improving the recent (3+𝜖)-approximation algorithm with 𝑂̃ (𝑛5/2+𝑂(log(1/𝜖)/log𝑛√)) running time of Bernstein and Roditty [Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011, pp. 1355--1365] in terms of both approximation and time guarantees. (2) We present a deterministic algorithm with a total update time of 𝑂̃ (𝑚𝑛/𝜖) and a query time of 𝑂(loglog𝑛). The algorithm has a multiplicative error of 1+𝜖 and gives the first improved deterministic algorithm since 1981. It also answers an open question raised by Bernstein in [Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, 2013, pp. 725--734]. The deterministic algorithm can be turned into a deterministic fully dynamic (1+𝜖)-approximation with an amortized update time of 𝑂̃ (𝑚𝑛/(𝜖𝑡)) and a query time of 𝑂̃ (𝑡) for every 𝑡≤𝑛√. In order to achieve our results, we introduce two new techniques: (i) A monotone Even--Shiloach tree algorithm which maintains a bounded-distance shortest-paths tree on a certain type of emulator called a locally persevering emulator. (ii) A derandomization technique based on moving Even--Shiloach trees as a way to derandomize the standard random set argument. These techniques might be of independent interest.","lang":"eng"}],"intvolume":" 45","status":"public","title":"Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization","_id":"11891","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"month":"05","quality_controlled":"1","main_file_link":[{"url":"https://arxiv.org/abs/1308.0776","open_access":"1"}],"external_id":{"arxiv":["1308.0776"]},"oa":1,"language":[{"iso":"eng"}],"doi":"10.1137/140957299","extern":"1","publisher":"Society for Industrial & Applied Mathematics","publication_status":"published","year":"2016","volume":45,"date_updated":"2023-02-17T14:21:40Z","date_created":"2022-08-17T08:37:00Z","author":[{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger"},{"first_name":"Sebastian","last_name":"Krinninger","full_name":"Krinninger, Sebastian"},{"full_name":"Nanongkai, Danupon","first_name":"Danupon","last_name":"Nanongkai"}]},{"scopus_import":"1","article_processing_charge":"No","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"day":"01","month":"03","citation":{"apa":"Henzinger, M. H., & King, V. (2001). Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/s0097539797327209","ieee":"M. H. Henzinger and V. King, “Maintaining minimum spanning forests in dynamic graphs,” SIAM Journal on Computing, vol. 31, no. 2. Society for Industrial & Applied Mathematics, pp. 364–374, 2001.","ista":"Henzinger MH, King V. 2001. Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing. 31(2), 364–374.","ama":"Henzinger MH, King V. Maintaining minimum spanning forests in dynamic graphs. SIAM Journal on Computing. 2001;31(2):364-374. doi:10.1137/s0097539797327209","chicago":"Henzinger, Monika H, and Valerie King. “Maintaining Minimum Spanning Forests in Dynamic Graphs.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2001. https://doi.org/10.1137/s0097539797327209.","short":"M.H. Henzinger, V. King, SIAM Journal on Computing 31 (2001) 364–374.","mla":"Henzinger, Monika H., and Valerie King. “Maintaining Minimum Spanning Forests in Dynamic Graphs.” SIAM Journal on Computing, vol. 31, no. 2, Society for Industrial & Applied Mathematics, 2001, pp. 364–74, doi:10.1137/s0097539797327209."},"publication":"SIAM Journal on Computing","page":"364-374","article_type":"original","quality_controlled":"1","doi":"10.1137/s0097539797327209","date_published":"2001-03-01T00:00:00Z","language":[{"iso":"eng"}],"type":"journal_article","issue":"2","abstract":[{"lang":"eng","text":"We present the first fully dynamic algorithm for maintaining a minimum spanning forest in time 𝑜(𝑛√) per operation. To be precise, the algorithm uses O(n1/3 log n) amortized time per update operation. The algorithm is fairly simple and deterministic. An immediate consequence is the first fully dynamic deterministic algorithm for maintaining connectivity and bipartiteness in amortized time O(n1/3 log n) per update, with O(1) worst case time per query."}],"extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11892","year":"2001","intvolume":" 31","publisher":"Society for Industrial & Applied Mathematics","publication_status":"published","title":"Maintaining minimum spanning forests in dynamic graphs","status":"public","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H"},{"first_name":"Valerie","last_name":"King","full_name":"King, Valerie"}],"volume":31,"oa_version":"None","date_created":"2022-08-17T08:43:43Z","date_updated":"2023-02-17T14:24:55Z"},{"scopus_import":"1","keyword":["directed graph","exploration algorithm"],"day":"01","article_processing_charge":"No","publication":"SIAM Journal on Computing","citation":{"apa":"Albers, S., & Henzinger, M. H. (2000). Exploring unknown environments. SIAM Journal on Computing. El Paso, TX, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/s009753979732428x","ieee":"S. Albers and M. H. Henzinger, “Exploring unknown environments,” SIAM Journal on Computing, vol. 29, no. 4. Society for Industrial and Applied Mathematics, pp. 1164–1188, 2000.","ista":"Albers S, Henzinger MH. 2000. Exploring unknown environments. SIAM Journal on Computing. 29(4), 1164–1188.","ama":"Albers S, Henzinger MH. Exploring unknown environments. SIAM Journal on Computing. 2000;29(4):1164-1188. doi:10.1137/s009753979732428x","chicago":"Albers, Susanne, and Monika H Henzinger. “Exploring Unknown Environments.” SIAM Journal on Computing. Society for Industrial and Applied Mathematics, 2000. https://doi.org/10.1137/s009753979732428x.","short":"S. Albers, M.H. Henzinger, SIAM Journal on Computing 29 (2000) 1164–1188.","mla":"Albers, Susanne, and Monika H. Henzinger. “Exploring Unknown Environments.” SIAM Journal on Computing, vol. 29, no. 4, Society for Industrial and Applied Mathematics, 2000, pp. 1164–88, doi:10.1137/s009753979732428x."},"article_type":"original","page":"1164-1188","date_published":"2000-07-01T00:00:00Z","type":"journal_article","abstract":[{"text":"We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The robot's task is to visit all nodes and edges of the graph using the minimum number R of edge traversals. Deng and Papadimitriou [Proceedings of the 31st Symposium on the Foundations of Computer Science, 1990, pp. 356-361] showed an upper bound for R ofd O(d)m and Koutsoupias (reported by Deng and Papadimitriou) gave a lower bound of Ω≠(d2m), where m is the number of edges in the graph and d is the minimum number of edges that have to be added to make the graph Eulerian. We give the 1rst subexponential algorithm for this exploration problem, which achieves an upper bound of dO(logd)m. We also show a matching lower bound of d≠(logd)m for our algorithm. Additionally, we give lower bounds of 2≠(d)m, respectively, d≠(logd)m for various other natural exploration algorithms.","lang":"eng"}],"issue":"4","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11694","title":"Exploring unknown environments","status":"public","intvolume":" 29","oa_version":"None","month":"07","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"quality_controlled":"1","conference":{"location":"El Paso, TX, United States","start_date":"1997-05-04","end_date":"1997-05-06","name":"STOC97: 29th Annual Symposium on Theory of Computing"},"doi":"10.1137/s009753979732428x","language":[{"iso":"eng"}],"extern":"1","year":"2000","acknowledgement":"We thank Prabhakar Raghavan for bringing to our attention the literature on the s-t connectivity problem. We also thank an anonymous referee for many helpful comments which improved the presentation of the paper.","publication_status":"published","publisher":"Society for Industrial and Applied Mathematics","author":[{"full_name":"Albers, Susanne","first_name":"Susanne","last_name":"Albers"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H"}],"date_updated":"2023-02-17T14:41:36Z","date_created":"2022-07-29T09:04:36Z","volume":29},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11893","year":"2000","publisher":"Society for Industrial & Applied Mathematics","intvolume":" 29","publication_status":"published","status":"public","title":"Improved data structures for fully dynamic biconnectivity","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H"}],"oa_version":"None","volume":29,"date_updated":"2023-02-17T14:39:47Z","date_created":"2022-08-17T08:45:41Z","type":"journal_article","issue":"6","abstract":[{"lang":"eng","text":"We present fully dynamic algorithms for maintaining the biconnected components in general and plane graphs.\r\n\r\nA fully dynamic algorithm maintains a graph during a sequence of insertions and deletions of edges or isolated vertices. Let m be the number of edges and n be the number of vertices in a graph. The time per operation of the best deterministic algorithms is 𝑂(𝑛√) in general graphs and O(log n) in plane graphs for fully dynamic connectivity and O(min m2/3 ,n}) in general graphs and 𝑂(𝑛√) in plane graphs for fully dynamic biconnectivity. We improve the later running times to 𝑂(𝑚log𝑛‾‾‾‾‾‾‾√) in general graphs and O(log 2n ) in plane graphs. Our algorithm for general graphscan also find the biconnected components of all vertices in time O(n)."}],"extern":"1","citation":{"chicago":"Henzinger, Monika H. “Improved Data Structures for Fully Dynamic Biconnectivity.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2000. https://doi.org/10.1137/s0097539794263907.","short":"M.H. Henzinger, SIAM Journal on Computing 29 (2000) 1761–1815.","mla":"Henzinger, Monika H. “Improved Data Structures for Fully Dynamic Biconnectivity.” SIAM Journal on Computing, vol. 29, no. 6, Society for Industrial & Applied Mathematics, 2000, pp. 1761–815, doi:10.1137/s0097539794263907.","ieee":"M. H. Henzinger, “Improved data structures for fully dynamic biconnectivity,” SIAM Journal on Computing, vol. 29, no. 6. Society for Industrial & Applied Mathematics, pp. 1761–1815, 2000.","apa":"Henzinger, M. H. (2000). Improved data structures for fully dynamic biconnectivity. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/s0097539794263907","ista":"Henzinger MH. 2000. Improved data structures for fully dynamic biconnectivity. SIAM Journal on Computing. 29(6), 1761–1815.","ama":"Henzinger MH. Improved data structures for fully dynamic biconnectivity. SIAM Journal on Computing. 2000;29(6):1761-1815. doi:10.1137/s0097539794263907"},"publication":"SIAM Journal on Computing","page":"1761-1815","article_type":"original","quality_controlled":"1","date_published":"2000-11-01T00:00:00Z","doi":"10.1137/s0097539794263907","language":[{"iso":"eng"}],"scopus_import":"1","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"article_processing_charge":"No","month":"11","day":"01"},{"page":"1138 - 1151","article_type":"original","citation":{"ista":"Chazelle B, Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M. 1994. Selecting heavily covered points. SIAM Journal on Computing. 23(6), 1138–1151.","ieee":"B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, and M. Sharir, “Selecting heavily covered points,” SIAM Journal on Computing, vol. 23, no. 6. SIAM, pp. 1138–1151, 1994.","apa":"Chazelle, B., Edelsbrunner, H., Guibas, L., Hershberger, J., Seidel, R., & Sharir, M. (1994). Selecting heavily covered points. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/S0097539790179919 ","ama":"Chazelle B, Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M. Selecting heavily covered points. SIAM Journal on Computing. 1994;23(6):1138-1151. doi:10.1137/S0097539790179919 ","chicago":"Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, John Hershberger, Raimund Seidel, and Micha Sharir. “Selecting Heavily Covered Points.” SIAM Journal on Computing. SIAM, 1994. https://doi.org/10.1137/S0097539790179919 .","mla":"Chazelle, Bernard, et al. “Selecting Heavily Covered Points.” SIAM Journal on Computing, vol. 23, no. 6, SIAM, 1994, pp. 1138–51, doi:10.1137/S0097539790179919 .","short":"B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, SIAM Journal on Computing 23 (1994) 1138–1151."},"publication":"SIAM Journal on Computing","date_published":"1994-12-01T00:00:00Z","scopus_import":"1","article_processing_charge":"No","day":"01","intvolume":" 23","title":"Selecting heavily covered points","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4033","oa_version":"None","type":"journal_article","issue":"6","abstract":[{"lang":"eng","text":"A collection of geometric selection lemmas is proved, such as the following: For any set P of n points in three-dimensional space and any set S of m spheres, where each sphere passes through a distinct point pair in P. there exists a point x, not necessarily in P, that is enclosed by Ω(m2/(n2 log6 n2/m)) of the spheres in S. Similar results apply in arbitrary fixed dimensions, and for geometric bodies other than spheres. The results have applications in reducing the size of geometric structures, such as three-dimensional Delaunay triangulations and Gabriel graphs, by adding extra points to their defining sets."}],"quality_controlled":"1","main_file_link":[{"url":"https://epubs.siam.org/doi/10.1137/S0097539790179919"}],"language":[{"iso":"eng"}],"doi":"10.1137/S0097539790179919 ","publication_identifier":{"issn":["0097-5397"]},"month":"12","publisher":"SIAM","publication_status":"published","year":"1994","volume":23,"date_created":"2018-12-11T12:06:33Z","date_updated":"2022-06-03T06:41:56Z","author":[{"first_name":"Bernard","last_name":"Chazelle","full_name":"Chazelle, Bernard"},{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert"},{"full_name":"Guibas, Leonidas","first_name":"Leonidas","last_name":"Guibas"},{"full_name":"Hershberger, John","last_name":"Hershberger","first_name":"John"},{"full_name":"Seidel, Raimund","last_name":"Seidel","first_name":"Raimund"},{"full_name":"Sharir, Micha","last_name":"Sharir","first_name":"Micha"}],"extern":"1","publist_id":"2092"},{"quality_controlled":"1","main_file_link":[{"url":"https://epubs.siam.org/doi/10.1137/0222031"}],"language":[{"iso":"eng"}],"doi":"10.1137/0222031","publication_identifier":{"issn":["0097-5397"]},"month":"04","publisher":"SIAM","publication_status":"published","acknowledgement":"National Science Foundation under grant CCR-89- 21421.","year":"1993","volume":22,"date_updated":"2022-03-29T13:25:02Z","date_created":"2018-12-11T12:06:35Z","author":[{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert"},{"first_name":"Raimund","last_name":"Seidel","full_name":"Seidel, Raimund"},{"full_name":"Sharir, Micha","last_name":"Sharir","first_name":"Micha"}],"extern":"1","publist_id":"2085","page":"418 - 429","article_type":"original","citation":{"short":"H. Edelsbrunner, R. Seidel, M. Sharir, SIAM Journal on Computing 22 (1993) 418–429.","mla":"Edelsbrunner, Herbert, et al. “On the Zone Theorem for Hyperplane Arrangements.” SIAM Journal on Computing, vol. 22, no. 2, SIAM, 1993, pp. 418–29, doi:10.1137/0222031.","chicago":"Edelsbrunner, Herbert, Raimund Seidel, and Micha Sharir. “On the Zone Theorem for Hyperplane Arrangements.” SIAM Journal on Computing. SIAM, 1993. https://doi.org/10.1137/0222031.","ama":"Edelsbrunner H, Seidel R, Sharir M. On the zone theorem for hyperplane arrangements. SIAM Journal on Computing. 1993;22(2):418-429. doi:10.1137/0222031","ieee":"H. Edelsbrunner, R. Seidel, and M. Sharir, “On the zone theorem for hyperplane arrangements,” SIAM Journal on Computing, vol. 22, no. 2. SIAM, pp. 418–429, 1993.","apa":"Edelsbrunner, H., Seidel, R., & Sharir, M. (1993). On the zone theorem for hyperplane arrangements. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0222031","ista":"Edelsbrunner H, Seidel R, Sharir M. 1993. On the zone theorem for hyperplane arrangements. SIAM Journal on Computing. 22(2), 418–429."},"publication":"SIAM Journal on Computing","date_published":"1993-04-01T00:00:00Z","scopus_import":"1","article_processing_charge":"No","day":"01","intvolume":" 22","status":"public","title":"On the zone theorem for hyperplane arrangements","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4041","oa_version":"None","type":"journal_article","issue":"2","abstract":[{"lang":"eng","text":"The zone theorem for an arrangement of n hyperplanes in d-dimensional real space says that the total number of faces bounding the cells intersected by another hyperplane is O(n(d-1)). This result is the basis of a time-optimal incremental algorithm that constructs a hyperplane arrangement and has a host of other algorithmic and combinatorial applications. Unfortunately, the original proof of the zone theorem, for d greater-than-or-equal-to 3, turned out to contain a serious and irreparable error. This paper presents a new proof of the theorem. The proof is based on an inductive argument, which also applies in the case of pseudohyperplane arrangements. The fallacies of the old proof along with some ways of partially saving that approach are briefly discussed."}]},{"scopus_import":"1","article_processing_charge":"No","day":"01","citation":{"chicago":"Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Jack Snoeyink. “Computing a Face in an Arrangement of Line Segments and Related Problems.” SIAM Journal on Computing. SIAM, 1993. https://doi.org/10.1137/0222077 .","mla":"Chazelle, Bernard, et al. “Computing a Face in an Arrangement of Line Segments and Related Problems.” SIAM Journal on Computing, vol. 22, no. 6, SIAM, 1993, pp. 1286–302, doi:10.1137/0222077 .","short":"B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, J. Snoeyink, SIAM Journal on Computing 22 (1993) 1286–1302.","ista":"Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Snoeyink J. 1993. Computing a face in an arrangement of line segments and related problems. SIAM Journal on Computing. 22(6), 1286–1302.","ieee":"B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Snoeyink, “Computing a face in an arrangement of line segments and related problems,” SIAM Journal on Computing, vol. 22, no. 6. SIAM, pp. 1286–1302, 1993.","apa":"Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., & Snoeyink, J. (1993). Computing a face in an arrangement of line segments and related problems. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0222077 ","ama":"Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Snoeyink J. Computing a face in an arrangement of line segments and related problems. SIAM Journal on Computing. 1993;22(6):1286-1302. doi:10.1137/0222077 "},"publication":"SIAM Journal on Computing","page":"1286 - 1302","article_type":"original","date_published":"1993-12-01T00:00:00Z","type":"journal_article","issue":"6","abstract":[{"text":"This paper presents a randomized incremental algorithm for computing a single face in an arrangement of n line segments in the plane that is fairly simple to implement. The expected running time of the algorithm is O(nα(n)log n). The analysis of the algorithm uses a novel approach that generalizes and extends the Clarkson-Shor analysis technique [in Discrete Comput. Geom., 4(1989), pp. 387-421]. A few extensions of the technique, obtaining efficient randomized incremental algorithms for constructing the entire arrangement of a collection of line segments and for computing a single face in an arrangement of Jordan arcs are also presented.","lang":"eng"}],"_id":"4036","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","intvolume":" 22","title":"Computing a face in an arrangement of line segments and related problems","status":"public","oa_version":"None","publication_identifier":{"issn":["0097-5397"]},"month":"12","main_file_link":[{"url":"https://epubs.siam.org/doi/10.1137/0222077"}],"quality_controlled":"1","doi":"10.1137/0222077 ","language":[{"iso":"eng"}],"publist_id":"2087","extern":"1","acknowledgement":"The authors wish to express their gratitude for the generous support and hospitality of the DEC Palo Alto Systems Research Center.","year":"1993","publisher":"SIAM","publication_status":"published","author":[{"last_name":"Chazelle","first_name":"Bernard","full_name":"Chazelle, Bernard"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert"},{"first_name":"Leonidas","last_name":"Guibas","full_name":"Guibas, Leonidas"},{"full_name":"Sharir, Micha","last_name":"Sharir","first_name":"Micha"},{"full_name":"Snoeyink, Jack","first_name":"Jack","last_name":"Snoeyink"}],"volume":22,"date_updated":"2022-03-30T08:07:21Z","date_created":"2018-12-11T12:06:34Z"},{"article_type":"original","page":"527 - 551","publication":"SIAM Journal on Computing","citation":{"mla":"Edelsbrunner, Herbert, and Tiow Tan. “A Quadratic Time Algorithm for the Minmax Length Triangulation.” SIAM Journal on Computing, vol. 22, no. 3, SIAM, 1993, pp. 527–51, doi:10.1137/0222036 .","short":"H. Edelsbrunner, T. Tan, SIAM Journal on Computing 22 (1993) 527–551.","chicago":"Edelsbrunner, Herbert, and Tiow Tan. “A Quadratic Time Algorithm for the Minmax Length Triangulation.” SIAM Journal on Computing. SIAM, 1993. https://doi.org/10.1137/0222036 .","ama":"Edelsbrunner H, Tan T. A quadratic time algorithm for the minmax length triangulation. SIAM Journal on Computing. 1993;22(3):527-551. doi:10.1137/0222036 ","ista":"Edelsbrunner H, Tan T. 1993. A quadratic time algorithm for the minmax length triangulation. SIAM Journal on Computing. 22(3), 527–551.","ieee":"H. Edelsbrunner and T. Tan, “A quadratic time algorithm for the minmax length triangulation,” SIAM Journal on Computing, vol. 22, no. 3. SIAM, pp. 527–551, 1993.","apa":"Edelsbrunner, H., & Tan, T. (1993). A quadratic time algorithm for the minmax length triangulation. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0222036 "},"date_published":"1993-06-01T00:00:00Z","scopus_import":"1","day":"01","article_processing_charge":"No","status":"public","title":"A quadratic time algorithm for the minmax length triangulation","intvolume":" 22","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4042","oa_version":"None","type":"journal_article","abstract":[{"text":"It is shown that a triangulation of a set of n points in the plane that minimizes the maximum edge length can be computed in time 0(n2). The algorithm is reasonably easy to implement and is based on the theorem that there is a triangulation with minmax edge length that contains the relative neighborhood graph of the points as a subgraph. With minor modifications the algorithm works for arbitrary normed metrics.","lang":"eng"}],"issue":"3","quality_controlled":"1","main_file_link":[{"url":"https://epubs.siam.org/doi/10.1137/0222036"}],"language":[{"iso":"eng"}],"doi":"10.1137/0222036 ","month":"06","publication_identifier":{"issn":["0097-5397"]},"publication_status":"published","publisher":"SIAM","acknowledgement":"The authors thank an anonymous referee for suggestions on the organization of this paper.","year":"1993","date_created":"2018-12-11T12:06:36Z","date_updated":"2022-03-30T07:43:13Z","volume":22,"author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert"},{"last_name":"Tan","first_name":"Tiow","full_name":"Tan, Tiow"}],"extern":"1","publist_id":"2086"},{"article_processing_charge":"No","day":"01","date_published":"1992-07-01T00:00:00Z","page":"994 - 1008","article_type":"original","citation":{"ama":"Edelsbrunner H, Tan T, Waupotitsch R. An O(n^2 log n) time algorithm for the MinMax angle triangulation. SIAM Journal on Scientific Computing. 1992;13(4):994-1008. doi:10.1137/0913058","apa":"Edelsbrunner, H., Tan, T., & Waupotitsch, R. (1992). An O(n^2 log n) time algorithm for the MinMax angle triangulation. SIAM Journal on Scientific Computing. Society for Industrial and Applied Mathematics . https://doi.org/10.1137/0913058","ieee":"H. Edelsbrunner, T. Tan, and R. Waupotitsch, “An O(n^2 log n) time algorithm for the MinMax angle triangulation,” SIAM Journal on Scientific Computing, vol. 13, no. 4. Society for Industrial and Applied Mathematics , pp. 994–1008, 1992.","ista":"Edelsbrunner H, Tan T, Waupotitsch R. 1992. An O(n^2 log n) time algorithm for the MinMax angle triangulation. SIAM Journal on Scientific Computing. 13(4), 994–1008.","short":"H. Edelsbrunner, T. Tan, R. Waupotitsch, SIAM Journal on Scientific Computing 13 (1992) 994–1008.","mla":"Edelsbrunner, Herbert, et al. “An O(N^2 Log n) Time Algorithm for the MinMax Angle Triangulation.” SIAM Journal on Scientific Computing, vol. 13, no. 4, Society for Industrial and Applied Mathematics , 1992, pp. 994–1008, doi:10.1137/0913058.","chicago":"Edelsbrunner, Herbert, Tiow Tan, and Roman Waupotitsch. “An O(N^2 Log n) Time Algorithm for the MinMax Angle Triangulation.” SIAM Journal on Scientific Computing. Society for Industrial and Applied Mathematics , 1992. https://doi.org/10.1137/0913058."},"publication":"SIAM Journal on Scientific Computing","issue":"4","abstract":[{"text":"It is shown that a triangulation of a set of n points in the plane that minimizes the maximum angle can be computed in time O(n2 log n) and space O(n). The algorithm is fairly easy to implement and is based on the edge-insertion scheme that iteratively improves an arbitrary initial triangulation. It can be extended to the case where edges are prescribed, and, within the same time- and space-bounds, it can lexicographically minimize the sorted angle vector if the point set is in general position. Experimental results on the efficiency of the algorithm and the quality of the triangulations obtained are included.","lang":"eng"}],"type":"journal_article","oa_version":"None","intvolume":" 13","title":"An O(n^2 log n) time algorithm for the MinMax angle triangulation","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4043","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"month":"07","language":[{"iso":"eng"}],"doi":"10.1137/0913058","quality_controlled":"1","main_file_link":[{"url":"https://epubs.siam.org/doi/10.1137/0913058"}],"extern":"1","publist_id":"2081","volume":13,"date_created":"2018-12-11T12:06:36Z","date_updated":"2022-03-16T09:35:05Z","author":[{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner"},{"full_name":"Tan, Tiow","last_name":"Tan","first_name":"Tiow"},{"last_name":"Waupotitsch","first_name":"Roman","full_name":"Waupotitsch, Roman"}],"publisher":"Society for Industrial and Applied Mathematics ","publication_status":"published","year":"1992"},{"article_processing_charge":"No","day":"01","page":"259 - 269","article_type":"original","citation":{"ama":"Edelsbrunner H, Shi W. An O(n log^2 h) time algorithm for the three-dimensional convex hull problem. SIAM Journal on Computing. 1991;20(2):259-269. doi:10.1137/0220016 ","ieee":"H. Edelsbrunner and W. Shi, “An O(n log^2 h) time algorithm for the three-dimensional convex hull problem,” SIAM Journal on Computing, vol. 20, no. 2. SIAM, pp. 259–269, 1991.","apa":"Edelsbrunner, H., & Shi, W. (1991). An O(n log^2 h) time algorithm for the three-dimensional convex hull problem. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0220016 ","ista":"Edelsbrunner H, Shi W. 1991. An O(n log^2 h) time algorithm for the three-dimensional convex hull problem. SIAM Journal on Computing. 20(2), 259–269.","short":"H. Edelsbrunner, W. Shi, SIAM Journal on Computing 20 (1991) 259–269.","mla":"Edelsbrunner, Herbert, and Weiping Shi. “An O(n Log^2 h) Time Algorithm for the Three-Dimensional Convex Hull Problem.” SIAM Journal on Computing, vol. 20, no. 2, SIAM, 1991, pp. 259–69, doi:10.1137/0220016 .","chicago":"Edelsbrunner, Herbert, and Weiping Shi. “An O(n Log^2 h) Time Algorithm for the Three-Dimensional Convex Hull Problem.” SIAM Journal on Computing. SIAM, 1991. https://doi.org/10.1137/0220016 ."},"publication":"SIAM Journal on Computing","date_published":"1991-04-01T00:00:00Z","type":"journal_article","issue":"2","abstract":[{"text":"An algorithm is presented that constructs the convex hull of a set of n points in three dimensions in worst-case time O(n log2h) and storage O(n), where h is the number of extreme points. This is an improvement of the O(nh) time gift-wrapping algorithm and, for certain values of h, of the O(n log n) time divide-and-conquer algorithm.","lang":"eng"}],"intvolume":" 20","title":"An O(n log^2 h) time algorithm for the three-dimensional convex hull problem","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4051","oa_version":"None","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"month":"04","quality_controlled":"1","main_file_link":[{"url":"https://epubs.siam.org/doi/10.1137/0220016"}],"language":[{"iso":"eng"}],"doi":"10.1137/0220016 ","extern":"1","publist_id":"2072","publisher":"SIAM","publication_status":"published","year":"1991","volume":20,"date_created":"2018-12-11T12:06:39Z","date_updated":"2022-03-02T10:18:31Z","author":[{"first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert"},{"first_name":"Weiping","last_name":"Shi","full_name":"Shi, Weiping"}]},{"extern":"1","publist_id":"2040","publication_status":"published","publisher":"SIAM","year":"1989","date_updated":"2022-02-11T07:55:48Z","date_created":"2018-12-11T12:06:50Z","volume":18,"author":[{"full_name":"Yao, F.","last_name":"Yao","first_name":"F."},{"last_name":"Dobkin","first_name":"David","full_name":"Dobkin, David"},{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner"},{"full_name":"Paterson, Michael","first_name":"Michael","last_name":"Paterson"}],"month":"04","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"quality_controlled":"1","main_file_link":[{"url":"https://epubs.siam.org/doi/10.1137/0218025","open_access":"1"}],"oa":1,"language":[{"iso":"eng"}],"doi":"10.1137/0218025","type":"journal_article","abstract":[{"text":"It is shown that, given a set S of n points in $R^3 $, one can always find three planes that form an eight-partition of S, that is, a partition where at most ${n / 8}$ points of S lie in each of the eight open regions. This theorem is used to define a data structure, called an octant tree, for representing any point set in $R^3 $. An octant tree for n points occupies $O(n)$ space and can be constructed in polynomial time. With this data structure and its refinements, efficient solutions to various range query problems in two and three dimensions can be obtained, including (1) half-space queries: find all points of S that lie to one side of any given plane; (2) polyhedron queries: find all points that lie inside (outside) any given polyhedron; and (3) circle queries in $R^2 $: for a planar set S, find all points that lie inside (outside) any given circle. The retrieval time for all these queries is $T(n) = O(n^\\alpha + m)$, where $\\alpha = 0.8988$ (or 0.8471 in case (3)), and m is the size of the output. This performance is the best currently known for linear-space data structures that can be deterministically constructed in polynomial time.","lang":"eng"}],"issue":"2","status":"public","title":"Partitioning space for range queries","intvolume":" 18","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4083","oa_version":"Published Version","scopus_import":"1","day":"01","article_processing_charge":"No","article_type":"original","page":"371 - 384","publication":"SIAM Journal on Computing","citation":{"ama":"Yao F, Dobkin D, Edelsbrunner H, Paterson M. Partitioning space for range queries. SIAM Journal on Computing. 1989;18(2):371-384. doi:10.1137/0218025","ista":"Yao F, Dobkin D, Edelsbrunner H, Paterson M. 1989. Partitioning space for range queries. SIAM Journal on Computing. 18(2), 371–384.","apa":"Yao, F., Dobkin, D., Edelsbrunner, H., & Paterson, M. (1989). Partitioning space for range queries. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0218025","ieee":"F. Yao, D. Dobkin, H. Edelsbrunner, and M. Paterson, “Partitioning space for range queries,” SIAM Journal on Computing, vol. 18, no. 2. SIAM, pp. 371–384, 1989.","mla":"Yao, F., et al. “Partitioning Space for Range Queries.” SIAM Journal on Computing, vol. 18, no. 2, SIAM, 1989, pp. 371–84, doi:10.1137/0218025.","short":"F. Yao, D. Dobkin, H. Edelsbrunner, M. Paterson, SIAM Journal on Computing 18 (1989) 371–384.","chicago":"Yao, F., David Dobkin, Herbert Edelsbrunner, and Michael Paterson. “Partitioning Space for Range Queries.” SIAM Journal on Computing. SIAM, 1989. https://doi.org/10.1137/0218025."},"date_published":"1989-04-01T00:00:00Z"},{"date_published":"1988-01-01T00:00:00Z","citation":{"ama":"Edelsbrunner H, Skiena S. Probing convex polygons with X-Rays. SIAM Journal on Computing. 1988;17(5):870-882. doi:10.1137/0217054 ","ista":"Edelsbrunner H, Skiena S. 1988. Probing convex polygons with X-Rays. SIAM Journal on Computing. 17(5), 870–882.","apa":"Edelsbrunner, H., & Skiena, S. (1988). Probing convex polygons with X-Rays. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0217054 ","ieee":"H. Edelsbrunner and S. Skiena, “Probing convex polygons with X-Rays,” SIAM Journal on Computing, vol. 17, no. 5. SIAM, pp. 870–882, 1988.","mla":"Edelsbrunner, Herbert, and Steven Skiena. “Probing Convex Polygons with X-Rays.” SIAM Journal on Computing, vol. 17, no. 5, SIAM, 1988, pp. 870–82, doi:10.1137/0217054 .","short":"H. Edelsbrunner, S. Skiena, SIAM Journal on Computing 17 (1988) 870–882.","chicago":"Edelsbrunner, Herbert, and Steven Skiena. “Probing Convex Polygons with X-Rays.” SIAM Journal on Computing. SIAM, 1988. https://doi.org/10.1137/0217054 ."},"publication":"SIAM Journal on Computing","page":"870 - 882","article_type":"original","article_processing_charge":"No","day":"01","scopus_import":"1","oa_version":"None","_id":"4091","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","intvolume":" 17","status":"public","title":"Probing convex polygons with X-Rays","issue":"5","abstract":[{"text":"An X-ray probe through a polygon measures the length of intersection between a line and the polygon. This paper considers the properties of various classes of X-ray probes, and shows how they interact to give finite strategies for completely describing convex n-gons. It is shown that (3n/2)+6 probes are sufficient to verify a specified n-gon, while for determining convex polygons (3n-1)/2 X-ray probes are necesssary and 5n+O(1) sufficient, with 3n+O(1) sufficient given that a lower bound on the size of the smallest edge of P is known.","lang":"eng"}],"type":"journal_article","doi":"10.1137/0217054 ","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://epubs.siam.org/doi/10.1137/0217054"}],"quality_controlled":"1","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"month":"01","author":[{"orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"},{"full_name":"Skiena, Steven","first_name":"Steven","last_name":"Skiena"}],"volume":17,"date_updated":"2022-02-08T11:14:23Z","date_created":"2018-12-11T12:06:53Z","acknowledgement":"The research of this author was supported by the Amoco Foundation Facility for the Development of Computer Science 1-6-44862.","year":"1988","publisher":"SIAM","publication_status":"published","publist_id":"2030","extern":"1"},{"scopus_import":"1","article_processing_charge":"No","day":"01","citation":{"apa":"Edelsbrunner, H., O’Rourke, J., & Seidel, R. (1986). Constructing arrangements of lines and hyperplanes with applications. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0215024","ieee":"H. Edelsbrunner, J. O’Rourke, and R. Seidel, “Constructing arrangements of lines and hyperplanes with applications,” SIAM Journal on Computing, vol. 15, no. 2. SIAM, pp. 341–363, 1986.","ista":"Edelsbrunner H, O’Rourke J, Seidel R. 1986. Constructing arrangements of lines and hyperplanes with applications. SIAM Journal on Computing. 15(2), 341–363.","ama":"Edelsbrunner H, O’Rourke J, Seidel R. Constructing arrangements of lines and hyperplanes with applications. SIAM Journal on Computing. 1986;15(2):341-363. doi:10.1137/0215024","chicago":"Edelsbrunner, Herbert, Joseph O’Rourke, and Raimund Seidel. “Constructing Arrangements of Lines and Hyperplanes with Applications.” SIAM Journal on Computing. SIAM, 1986. https://doi.org/10.1137/0215024.","short":"H. Edelsbrunner, J. O’Rourke, R. Seidel, SIAM Journal on Computing 15 (1986) 341–363.","mla":"Edelsbrunner, Herbert, et al. “Constructing Arrangements of Lines and Hyperplanes with Applications.” SIAM Journal on Computing, vol. 15, no. 2, SIAM, 1986, pp. 341–63, doi:10.1137/0215024."},"publication":"SIAM Journal on Computing","page":"341 - 363","article_type":"original","date_published":"1986-01-01T00:00:00Z","type":"journal_article","issue":"2","abstract":[{"lang":"eng","text":"A finite set of lines partitions the Euclidean plane into a cell complex. Similarly, a finite set of $(d - 1)$-dimensional hyperplanes partitions $d$-dimensional Euclidean space. An algorithm is presented that constructs a representation for the cell complex defined by $n$ hyperplanes in optimal $O(n^d )$ time in $d$ dimensions. It relies on a combinatorial result that is of interest in its own right. The algorithm is shown to lead to new methods for computing $\\lambda $-matrices, constructing all higher-order Voronoi diagrams, halfspatial range estimation, degeneracy testing, and finding minimum measure simplices. In all five applications, the new algorithms are asymptotically faster than previous results, and in several cases are the only known methods that generalize to arbitrary dimensions. The algorithm also implies an upper bound of $2^{cn^d } $, $c$ a positive constant, for the number of combinatorially distinct arrangements of $n$ hyperplanes in $E^d $.\r\n© 1986 Society for Industrial and Applied Mathematics"}],"_id":"4105","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","intvolume":" 15","title":"Constructing arrangements of lines and hyperplanes with applications","status":"public","oa_version":"None","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"month":"01","quality_controlled":"1","doi":"10.1137/0215024","language":[{"iso":"eng"}],"publist_id":"2017","extern":"1","acknowledgement":"We thank Emmerich Welzl for discussions on Theorem 2.7. We also thank Friedrich Huber for implementing the \r\nconstruction of arrangements in arbitrary dimensions, and Gerd Stoeckl for implementing the algorithms presented in §§\r\n4.1 and 4.3. The third author wishes to thank Jack Edmonds for the many enlightening discussions.\r\n","year":"1986","publisher":"SIAM","publication_status":"published","author":[{"last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"full_name":"O'Rourke, Joseph","first_name":"Joseph","last_name":"O'Rourke"},{"last_name":"Seidel","first_name":"Raimund","full_name":"Seidel, Raimund"}],"volume":15,"date_created":"2018-12-11T12:06:58Z","date_updated":"2022-02-01T11:03:07Z"},{"month":"01","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"language":[{"iso":"eng"}],"doi":"10.1137/0215023","quality_controlled":"1","extern":"1","publist_id":"2016","date_updated":"2022-02-01T10:05:55Z","date_created":"2018-12-11T12:06:58Z","volume":15,"author":[{"orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"},{"first_name":"Leonidas","last_name":"Guibas","full_name":"Guibas, Leonidas"},{"first_name":"Jorge","last_name":"Stolfi","full_name":"Stolfi, Jorge"}],"publication_status":"published","publisher":"SIAM","acknowledgement":"We would like to thank Andrei Broder, Dan Greene, Mary Claire van Leunen, Greg Nelson, Lyle Ramshaw, and F. Frances Yao, whose comments and suggestions have greatly improved the readability of this paper.","year":"1986","day":"01","article_processing_charge":"No","scopus_import":"1","date_published":"1986-01-01T00:00:00Z","article_type":"original","page":"317 - 340","publication":"SIAM Journal on Computing","citation":{"chicago":"Edelsbrunner, Herbert, Leonidas Guibas, and Jorge Stolfi. “Optimal Point Location in a Monotone Subdivision.” SIAM Journal on Computing. SIAM, 1986. https://doi.org/10.1137/0215023.","mla":"Edelsbrunner, Herbert, et al. “Optimal Point Location in a Monotone Subdivision.” SIAM Journal on Computing, vol. 15, no. 2, SIAM, 1986, pp. 317–40, doi:10.1137/0215023.","short":"H. Edelsbrunner, L. Guibas, J. Stolfi, SIAM Journal on Computing 15 (1986) 317–340.","ista":"Edelsbrunner H, Guibas L, Stolfi J. 1986. Optimal point location in a monotone subdivision. SIAM Journal on Computing. 15(2), 317–340.","apa":"Edelsbrunner, H., Guibas, L., & Stolfi, J. (1986). Optimal point location in a monotone subdivision. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0215023","ieee":"H. Edelsbrunner, L. Guibas, and J. Stolfi, “Optimal point location in a monotone subdivision,” SIAM Journal on Computing, vol. 15, no. 2. SIAM, pp. 317–340, 1986.","ama":"Edelsbrunner H, Guibas L, Stolfi J. Optimal point location in a monotone subdivision. SIAM Journal on Computing. 1986;15(2):317-340. doi:10.1137/0215023"},"abstract":[{"lang":"eng","text":"Point location, often known in graphics as “hit detection,” is one of the fundamental problems of computational geometry. In a point location query we want to identify which of a given collection of geometric objects contains a particular point. Let $\\mathcal{S}$ denote a subdivision of the Euclidean plane into monotone regions by a straight-line graph of $m$ edges. In this paper we exhibit a substantial refinement of the technique of Lee and Preparata [SIAM J. Comput., 6 (1977), pp. 594–606] for locating a point in $\\mathcal{S}$ based on separating chains. The new data structure, called a layered dag, can be built in $O(m)$ time, uses $O(m)$ storage, and makes possible point location in $O(\\log m)$ time. Unlike previous structures that attain these optimal bounds, the layered dag can be implemented in a simple and practical way, and is extensible to subdivisions with edges more general than straight-line segments.\r\n© 1986 Society for Industrial and Applied Mathematics"}],"issue":"2","type":"journal_article","oa_version":"None","status":"public","title":"Optimal point location in a monotone subdivision","intvolume":" 15","_id":"4104","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17"},{"year":"1986","publisher":"SIAM","publication_status":"published","author":[{"full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833"},{"full_name":"Welzl, Emo","last_name":"Welzl","first_name":"Emo"}],"volume":15,"date_created":"2018-12-11T12:07:00Z","date_updated":"2022-02-01T09:34:20Z","publist_id":"2014","extern":"1","quality_controlled":"1","doi":"10.1137/0215019","language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"month":"01","_id":"4110","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","intvolume":" 15","title":"Constructing belts in two-dimensional arrangements with applications","status":"public","oa_version":"None","type":"journal_article","issue":"1","abstract":[{"text":"For H a set of lines in the Euclidean plane, $A(H)$ denotes the induced dissection, called the arrangement of H. We define the notion of a belt in $A(H)$, which is bounded by a subset of the edges in $A(H)$, and describe two algorithms for constructing belts. All this is motivated by applications to a host of seemingly unrelated problems including a type of range search and finding the minimum area triangle with the vertices taken from some finite set of points.","lang":"eng"}],"citation":{"mla":"Edelsbrunner, Herbert, and Emo Welzl. “Constructing Belts in Two-Dimensional Arrangements with Applications.” SIAM Journal on Computing, vol. 15, no. 1, SIAM, 1986, pp. 271–84, doi:10.1137/0215019.","short":"H. Edelsbrunner, E. Welzl, SIAM Journal on Computing 15 (1986) 271–284.","chicago":"Edelsbrunner, Herbert, and Emo Welzl. “Constructing Belts in Two-Dimensional Arrangements with Applications.” SIAM Journal on Computing. SIAM, 1986. https://doi.org/10.1137/0215019.","ama":"Edelsbrunner H, Welzl E. Constructing belts in two-dimensional arrangements with applications. SIAM Journal on Computing. 1986;15(1):271-284. doi:10.1137/0215019","ista":"Edelsbrunner H, Welzl E. 1986. Constructing belts in two-dimensional arrangements with applications. SIAM Journal on Computing. 15(1), 271–284.","ieee":"H. Edelsbrunner and E. Welzl, “Constructing belts in two-dimensional arrangements with applications,” SIAM Journal on Computing, vol. 15, no. 1. SIAM, pp. 271–284, 1986.","apa":"Edelsbrunner, H., & Welzl, E. (1986). Constructing belts in two-dimensional arrangements with applications. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0215019"},"publication":"SIAM Journal on Computing","page":"271 - 284","article_type":"original","date_published":"1986-01-01T00:00:00Z","scopus_import":"1","article_processing_charge":"No","day":"01"}]