[{"conference":{"location":"Virtual ","end_date":"2020-09-25","start_date":"2020-09-20","name":"EMSOFT: International Conference on Embedded Software"},"language":[{"iso":"eng"}],"keyword":["reachability","hybrid systems","decomposition"],"oa_version":"Preprint","project":[{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"grant_number":"Z00312","name":"The Wittgenstein Prize","_id":"25C5A090-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships"}],"publication":"Proceedings of the International Conference on Embedded Software","has_accepted_license":"1","status":"public","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","related_material":{"record":[{"relation":"later_version","id":"8790","status":"public"}]},"file":[{"access_level":"open_access","relation":"main_file","success":1,"creator":"cschilli","file_id":"8288","checksum":"d19e97d0f8a3a441dc078ec812297d75","file_size":696384,"date_created":"2020-08-24T12:53:15Z","content_type":"application/pdf","file_name":"2020EMSOFT.pdf","date_updated":"2020-08-24T12:53:15Z"}],"oa":1,"date_published":"2020-01-01T00:00:00Z","type":"conference","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"file_date_updated":"2020-08-24T12:53:15Z","quality_controlled":"1","ec_funded":1,"title":"Reachability analysis of linear hybrid systems via block decomposition","publication_status":"published","article_processing_charge":"No","date_created":"2020-08-24T12:56:20Z","department":[{"_id":"ToHe"}],"author":[{"first_name":"Sergiy","last_name":"Bogomolov","full_name":"Bogomolov, Sergiy"},{"full_name":"Forets, Marcelo","first_name":"Marcelo","last_name":"Forets"},{"full_name":"Frehse, Goran","first_name":"Goran","last_name":"Frehse"},{"full_name":"Potomkin, Kostiantyn","first_name":"Kostiantyn","last_name":"Potomkin"},{"id":"3A2F4DCE-F248-11E8-B48F-1D18A9856A87","full_name":"Schilling, Christian","orcid":"0000-0003-3658-1065","last_name":"Schilling","first_name":"Christian"}],"_id":"8287","ddc":["000"],"abstract":[{"lang":"eng","text":"Reachability analysis aims at identifying states reachable by a system within a given time horizon. This task is known to be computationally expensive for linear hybrid systems. Reachability analysis works by iteratively applying continuous and discrete post operators to compute states reachable according to continuous and discrete dynamics, respectively. In this paper, we enhance both of these operators and make sure that most of the involved computations are performed in low-dimensional state space. In particular, we improve the continuous-post operator by performing computations in high-dimensional state space only for time intervals relevant for the subsequent application of the discrete-post operator. Furthermore, the new discrete-post operator performs low-dimensional computations by leveraging the structure of the guard and assignment of a considered transition. We illustrate the potential of our approach on a number of challenging benchmarks."}],"arxiv":1,"external_id":{"arxiv":["1905.02458"]},"date_updated":"2023-08-22T13:27:32Z","year":"2020","citation":{"ista":"Bogomolov S, Forets M, Frehse G, Potomkin K, Schilling C. 2020. Reachability analysis of linear hybrid systems via block decomposition. Proceedings of the International Conference on Embedded Software. EMSOFT: International Conference on Embedded Software.","mla":"Bogomolov, Sergiy, et al. “Reachability Analysis of Linear Hybrid Systems via Block Decomposition.” <i>Proceedings of the International Conference on Embedded Software</i>, 2020.","short":"S. Bogomolov, M. Forets, G. Frehse, K. Potomkin, C. Schilling, in:, Proceedings of the International Conference on Embedded Software, 2020.","ieee":"S. Bogomolov, M. Forets, G. Frehse, K. Potomkin, and C. Schilling, “Reachability analysis of linear hybrid systems via block decomposition,” in <i>Proceedings of the International Conference on Embedded Software</i>, Virtual , 2020.","chicago":"Bogomolov, Sergiy, Marcelo Forets, Goran Frehse, Kostiantyn Potomkin, and Christian Schilling. “Reachability Analysis of Linear Hybrid Systems via Block Decomposition.” In <i>Proceedings of the International Conference on Embedded Software</i>, 2020.","ama":"Bogomolov S, Forets M, Frehse G, Potomkin K, Schilling C. Reachability analysis of linear hybrid systems via block decomposition. In: <i>Proceedings of the International Conference on Embedded Software</i>. ; 2020.","apa":"Bogomolov, S., Forets, M., Frehse, G., Potomkin, K., &#38; Schilling, C. (2020). Reachability analysis of linear hybrid systems via block decomposition. In <i>Proceedings of the International Conference on Embedded Software</i>. Virtual ."}},{"author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"},{"full_name":"Guibas, Leonidas","first_name":"Leonidas","last_name":"Guibas"},{"full_name":"Pach, János","last_name":"Pach","first_name":"János"},{"full_name":"Pollack, Richard","first_name":"Richard","last_name":"Pollack"},{"full_name":"Seidel, Raimund","first_name":"Raimund","last_name":"Seidel"},{"full_name":"Sharir, Micha","first_name":"Micha","last_name":"Sharir"}],"scopus_import":"1","_id":"4097","intvolume":"       317","alternative_title":["LNCS"],"title":"Arrangements of curves in the plane - topology, combinatorics, and algorithms","article_processing_charge":"No","date_created":"2018-12-11T12:06:55Z","publication_status":"published","quality_controlled":"1","page":"214 - 229","publisher":"Springer","citation":{"short":"H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, M. Sharir, in:, 15th International Colloquium on Automata, Languages and Programming, Springer, 1988, pp. 214–229.","mla":"Edelsbrunner, Herbert, et al. “Arrangements of Curves in the Plane - Topology, Combinatorics, and Algorithms.” <i>15th International Colloquium on Automata, Languages and Programming</i>, vol. 317, Springer, 1988, pp. 214–29, doi:<a href=\"https://doi.org/10.1007/3-540-19488-6_118\">10.1007/3-540-19488-6_118</a>.","ista":"Edelsbrunner H, Guibas L, Pach J, Pollack R, Seidel R, Sharir M. 1988. Arrangements of curves in the plane - topology, combinatorics, and algorithms. 15th International Colloquium on Automata, Languages and Programming. ICALP: Automata, Languages and Programming, LNCS, vol. 317, 214–229.","apa":"Edelsbrunner, H., Guibas, L., Pach, J., Pollack, R., Seidel, R., &#38; Sharir, M. (1988). Arrangements of curves in the plane - topology, combinatorics, and algorithms. In <i>15th International Colloquium on Automata, Languages and Programming</i> (Vol. 317, pp. 214–229). Tampere, Finland: Springer. <a href=\"https://doi.org/10.1007/3-540-19488-6_118\">https://doi.org/10.1007/3-540-19488-6_118</a>","ama":"Edelsbrunner H, Guibas L, Pach J, Pollack R, Seidel R, Sharir M. Arrangements of curves in the plane - topology, combinatorics, and algorithms. In: <i>15th International Colloquium on Automata, Languages and Programming</i>. Vol 317. Springer; 1988:214-229. doi:<a href=\"https://doi.org/10.1007/3-540-19488-6_118\">10.1007/3-540-19488-6_118</a>","ieee":"H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, and M. Sharir, “Arrangements of curves in the plane - topology, combinatorics, and algorithms,” in <i>15th International Colloquium on Automata, Languages and Programming</i>, Tampere, Finland, 1988, vol. 317, pp. 214–229.","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, János Pach, Richard Pollack, Raimund Seidel, and Micha Sharir. “Arrangements of Curves in the Plane - Topology, Combinatorics, and Algorithms.” In <i>15th International Colloquium on Automata, Languages and Programming</i>, 317:214–29. Springer, 1988. <a href=\"https://doi.org/10.1007/3-540-19488-6_118\">https://doi.org/10.1007/3-540-19488-6_118</a>."},"year":"1988","date_updated":"2022-02-08T10:15:09Z","abstract":[{"text":"Arrangements of curves in the plane are of fundamental significance in many problems of computational and combinatorial geometry (e.g. motion planning, algebraic cell decomposition, etc.). In this paper we study various topological and combinatorial properties of such arrangements under some mild assumptions on the shape of the curves, and develop basic tools for the construction, manipulation, and analysis of these arrangements. Our main results include a generalization of the zone theorem of [EOS], [CGL] to arrangements of curves (in which we show that the combinatorial complexity of the zone of a curve is nearly linear in the number of curves), and an application of (some weaker variant of) that theorem to obtain a nearly quadratic incremental algorithm for the construction of such arrangements.","lang":"eng"}],"day":"01","doi":"10.1007/3-540-19488-6_118","extern":"1","volume":317,"acknowledgement":"Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by the National Science Foundation under grant CCR-8714566. Work on this paper by the third and sixth authors has been supported by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation. Work by the sixth author has also been supported by a research grant from the NCRD — the Israeli National Council for Research and Development. Work by the fourth author has been supported by National Science Foundation Grant DMS-8501947.","publication":"15th International Colloquium on Automata, Languages and Programming","month":"01","oa_version":"None","keyword":["line segment","computational geometry","Jordan curve","cell decomposition","vertical tangency"],"language":[{"iso":"eng"}],"conference":{"name":"ICALP: Automata, Languages and Programming","start_date":"1988-07-11","end_date":"1988-07-15","location":"Tampere, Finland"},"type":"conference","date_published":"1988-01-01T00:00:00Z","publist_id":"2028","publication_identifier":{"isbn":["978-3-540-19488-0"]},"status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","main_file_link":[{"url":"https://link.springer.com/chapter/10.1007/3-540-19488-6_118"}]}]