---
_id: '8287'
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.
article_processing_charge: No
arxiv: 1
author:
- first_name: Sergiy
  full_name: Bogomolov, Sergiy
  last_name: Bogomolov
- first_name: Marcelo
  full_name: Forets, Marcelo
  last_name: Forets
- first_name: Goran
  full_name: Frehse, Goran
  last_name: Frehse
- first_name: Kostiantyn
  full_name: Potomkin, Kostiantyn
  last_name: Potomkin
- first_name: Christian
  full_name: Schilling, Christian
  id: 3A2F4DCE-F248-11E8-B48F-1D18A9856A87
  last_name: Schilling
  orcid: 0000-0003-3658-1065
citation:
  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 .
  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.
  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.
  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.
conference:
  end_date: 2020-09-25
  location: 'Virtual '
  name: 'EMSOFT: International Conference on Embedded Software'
  start_date: 2020-09-20
date_created: 2020-08-24T12:56:20Z
date_published: 2020-01-01T00:00:00Z
date_updated: 2023-08-22T13:27:32Z
ddc:
- '000'
department:
- _id: ToHe
ec_funded: 1
external_id:
  arxiv:
  - '1905.02458'
file:
- access_level: open_access
  checksum: d19e97d0f8a3a441dc078ec812297d75
  content_type: application/pdf
  creator: cschilli
  date_created: 2020-08-24T12:53:15Z
  date_updated: 2020-08-24T12:53:15Z
  file_id: '8288'
  file_name: 2020EMSOFT.pdf
  file_size: 696384
  relation: main_file
  success: 1
file_date_updated: 2020-08-24T12:53:15Z
has_accepted_license: '1'
keyword:
- reachability
- hybrid systems
- decomposition
language:
- iso: eng
oa: 1
oa_version: Preprint
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 25C5A090-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z00312
  name: The Wittgenstein Prize
- _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
publication_status: published
quality_controlled: '1'
related_material:
  record:
  - id: '8790'
    relation: later_version
    status: public
status: public
title: Reachability analysis of linear hybrid systems via block decomposition
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2020'
...
---
_id: '4097'
abstract:
- lang: eng
  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.
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.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
- first_name: János
  full_name: Pach, János
  last_name: Pach
- first_name: Richard
  full_name: Pollack, Richard
  last_name: Pollack
- first_name: Raimund
  full_name: Seidel, Raimund
  last_name: Seidel
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
citation:
  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>'
  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>'
  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>.
  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.
  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.'
  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>.
  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.
conference:
  end_date: 1988-07-15
  location: Tampere, Finland
  name: 'ICALP: Automata, Languages and Programming'
  start_date: 1988-07-11
date_created: 2018-12-11T12:06:55Z
date_published: 1988-01-01T00:00:00Z
date_updated: 2022-02-08T10:15:09Z
day: '01'
doi: 10.1007/3-540-19488-6_118
extern: '1'
intvolume: '       317'
keyword:
- line segment
- computational geometry
- Jordan curve
- cell decomposition
- vertical tangency
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/chapter/10.1007/3-540-19488-6_118
month: '01'
oa_version: None
page: 214 - 229
publication: 15th International Colloquium on Automata, Languages and Programming
publication_identifier:
  isbn:
  - 978-3-540-19488-0
publication_status: published
publisher: Springer
publist_id: '2028'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Arrangements of curves in the plane - topology, combinatorics, and algorithms
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 317
year: '1988'
...