Skip to content

References

Jump to bottom
Marcelo Forets edited this page Jan 11, 2021 · 52 revisions

Zonotopes

  • Kochdumper, Niklas, and Matthias Althoff. "Representation of Polytopes as Polynomial Zonotopes." arXiv preprint arXiv:1910.07271 (2019). https://arxiv.org/pdf/1910.07271.pdf

  • Kochdumper N, Althoff M. Constrained Polynomial Zonotopes. arXiv preprint arXiv:2005.08849. 2020 May 18. https://arxiv.org/pdf/2005.08849.pdf

  • Raghuraman, Vignesh, and Justin P. Koeln. "Set operations and order reductions for constrained zonotopes." arXiv preprint arXiv:2009.06039 (2020). pdf

  • Guibas, L. J., Nguyen, A. T., & Zhang, L. (2003, January). Zonotopes as bounding volumes. In SODA (Vol. 3, pp. 803-812). pdf

  • Althoff, M., Stursberg, O., & Buss, M. (2010). Computing reachable sets of hybrid systems using a combination of zonotopes and polytopes. Nonlinear analysis: hybrid systems, 4(2), 233-249. pdf

  • Althoff, M., & Krogh, B. H. (2012, April). Avoiding geometric intersection operations in reachability analysis of hybrid systems. In Proceedings of the 15th ACM international conference on Hybrid Systems: Computation and Control (pp. 45-54). pdf

  • Gurung, A., & Ray, R. (2016). An Efficient Algorithm for Vertex Enumeration of Two-Dimensional Projection of Polytopes. arXiv preprint arXiv:1611.10059. pdf Amit Gurung and Rajarshi Ray.

  • Zonotopes Techniques for Reachability Analysis. A. Girard. slides

  • Ferrez, J. A., Fukuda, K., & Liebling, T. M. (2005). Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm. European Journal of Operational Research, 166(1), 35-50. pdf

  • Fukuda, K. (2004). From the zonotope construction to the Minkowski addition of convex polytopes. Journal of Symbolic Computation, 38(4), 1261-1272. pdf

  • Deza, A., & Pournin, L. (2019). A linear optimization oracle for zonotope computation. arXiv preprint arXiv:1912.02439. pdf

  • Stinson, K., Gleich, D. F., & Constantine, P. G. (2016). A randomized algorithm for enumerating zonotope vertices. arXiv preprint arXiv:1602.06620. pdf

  • Girard, A., & Le Guernic, C. (2008, April). Zonotope/hyperplane intersection for hybrid systems reachability analysis. In International Workshop on Hybrid Systems: Computation and Control (pp. 215-228). Springer, Berlin, Heidelberg. pdf

  • Althoff, M., & Krogh, B. H. (2011, December). Zonotope bundles for the efficient computation of reachable sets. In 2011 50th IEEE conference on decision and control and European control conference (pp. 6814-6821). IEEE. pdf

  • Kochdumper, N., & Althoff, M. (2019). Sparse polynomial zonotopes: A novel set representation for reachability analysis. arXiv preprint arXiv:1901.01780. pdf

  • Althoff, M., & Frehse, G. (2016, December). Combining zonotopes and support functions for efficient reachability analysis of linear systems. In 2016 IEEE 55th Conference on Decision and Control (CDC) (pp. 7439-7446). IEEE. pdf

  • Yang, X., & Scott, J. K. (2018). A comparison of zonotope order reduction techniques. Automatica, 95, 378-384. pdf

  • Althoff, M., Stursberg, O., & Buss, M. (2008). Verification of uncertain embedded systems by computing reachable sets based on zonotopes. IFAC Proceedings Volumes, 41(2), 5125-5130. pdf

  • Rego, B. S., Raffo, G. V., Scott, J. K., & Raimondo, D. M. (2020). Guaranteed methods based on constrained zonotopes for set-valued state estimation of nonlinear discrete-time systems. Automatica, 111, 108614. pdf

  • Kopetzki, A. K., Schürmann, B., & Althoff, M. (2017, December). Methods for order reduction of zonotopes. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC) (pp. 5626-5633). IEEE. pdf

  • Maiga, M., Ramdani, N., Travé-Massuyès, L., & Combastel, C. (2015). A comprehensive method for reachability analysis of uncertain nonlinear hybrid systems. IEEE Transactions on Automatic Control, 61(9), 2341-2356. pdf

  • Scott, J. K., Raimondo, D. M., Marseglia, G. R., & Braatz, R. D. (2016). Constrained zonotopes: A new tool for set-based estimation and fault detection. Automatica, 69, 126-136. pdf

  • Althoff, M. (2015). On computing the minkowski difference of zonotopes. arXiv preprint arXiv:1512.02794. pdf

Polyhedra

  • Avis, D., & Fukuda, K. (1996). Reverse search for enumeration. Discrete applied mathematics, 65(1-3), 21-46. pdf

  • Preparata, F. P., & Muller, D. E. (1979). Finding the intersection of n half-spaces in time O (n log n). Theoretical Computer Science, 8(1), 45-55. pdf

  • Muller, D. E., & Preparata, F. P. (1978). Finding the intersection of two convex polyhedra. Theoretical Computer Science, 7(2), 217-236. pdf

  • Stinson, K., Gleich, D. F., & Constantine, P. G. (2016). A randomized algorithm for enumerating zonotope vertices. arXiv preprint arXiv:1602.06620. pdf, groundai

  • Walkup, David, and Roger Wets. "Lifting projections of convex polyhedra." Pacific Journal of Mathematics 28.2 (1969): 465-475. pdf

Minkowski sum

Minkowski difference

Triangulations

Polygon intersection

More on intersections

Disjointness check

  • Chazelle, B., & Dobkin, D. P. (1980, April). Detection is easier than computation. In Proceedings of the twelfth annual ACM symposium on Theory of computing (pp. 146-153).

Enumerations

  • Löhne, A. (2020). Approximate Vertex Enumeration. arXiv preprint arXiv:2007.06325.

  • Awasthi, P., Kalantari, B., & Zhang, Y. (2018, March). Robust vertex enumeration for convex hulls in high dimensions. In International Conference on Artificial Intelligence and Statistics (pp. 1387-1396).

Star sets

  • Tran, H. D., Lopez, D. M., Musau, P., Yang, X., Nguyen, L. V., Xiang, W., & Johnson, T. T. (2019, October). Star-based reachability analysis of deep neural networks. In International Symposium on Formal Methods (pp. 670-686). Springer, Cham. pdf

Theses

  • Le Guernic, C. (2009). Reachability analysis of hybrid systems with linear continuous dynamics (Doctoral dissertation). pdf. Tags: support function, zonotope, zonotope-hyperplane intersection.

  • Althoff, M. (2010). Reachability analysis and its application to the safety assessment of autonomous cars (Doctoral dissertation, Technische Universität München). pdf, M. Althoff's PhD thesis. Tags: zonotope, zonotope order reduction, interval matrix, matrix zonotope.

  • Froitzheim, S. (2016). Efficient conversion of geometric state set representations for hybrid systems (Doctoral dissertation, Bachelor’s thesis, RWTH Aachen University). pdf

Clone this wiki locally