Conference item icon

Conference item

How fast can you escape a compact polytope?

Abstract:
The Continuous Polytope Escape Problem (CPEP) asks whether every trajectory of a linear differential equation initialised within a convex polytope eventually escapes the polytope. We provide a polynomial-time algorithm to decide CPEP for compact polytopes. We also establish a quantitative uniform upper bound on the time required for every trajectory to escape the given polytope. In addition, we establish iteration bounds for termination of discrete linear loops via reduction to the continuous case.
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.STACS.2020.49
Publication website:
https://stacs2020.sciencesconf.org/

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Sub department:
Computer Science
Oxford college:
St John's College
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Sub department:
Computer Science
Role:
Author
Publisher:
Schloss Dagstuhl Publisher's website
Pages:
49:1--49:11
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Series number:
154
Host title:
37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Place of publication:
Dagstuhl, Germany
Publication date:
2020-02-27
Acceptance date:
2019-12-20
Event title:
37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Event location:
Montpellier, France
Event website:
https://stacs2020.sciencesconf.org/
Event start date:
2020-03-10T00:00:00Z
Event end date:
2020-03-13T00:00:00Z
DOI:
ISSN:
1868-8969
ISBN:
978-3-95977-140-5
Language:
English
Keywords:
Pubs id:
1084192
Local pid:
pubs:1084192
Deposit date:
2020-01-31

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP