References

Zonotopes

• 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

Minkowski sum

• https://hal.archives-ouvertes.fr/hal-01092060/document
• https://pdfs.semanticscholar.org/7492/2769a31a4d6695f3ada51b05134f77b4fe5b.pdf
• https://arxiv.org/pdf/1810.01587.pdf

Minkowski difference

• https://en.wikipedia.org/wiki/Minkowski_addition
• On Computing the Minkowski Difference of Zonotopes. Matthias Althoff.
• Theory and computation of disturbance invariant sets for discrete-time linear systems. Ilya Kolmanovsky and Elmer G. Gilbert.
• The Minkowski Difference for Convex Polyhedra and Some its Applications. Z. R. Gabidullina.

Triangulations

• https://github.com/JuliaGeometry/TetGen.jl
• https://github.com/gridap/MiniQhull.jl
  • https://apps.fedoraproject.org/packages/s/libqhull
• https://github.com/JuliaGeometry/VoronoiDelaunay.jl/issues/8
• https://github.com/JuliaPDE/SurveyofPDEPackages
• http://www.personal.psu.edu/cxc11/AERSP560/DELAUNEY/13_Two_algorithms_Delauney.pdf
• https://www.codeproject.com/Articles/587629/A-Delaunay-triangulation-function-in-C
• https://github.com/esimov/triangle
• http://algorist.com/problems/Triangulation.html
• http://algorist.com/sections/Computational_Geometry.html
• http://www.qhull.org/
• http://www.cs.cmu.edu/~quake/triangle.research.html
• Walking through triangulation: https://hal.inria.fr/inria-00102194/document

Polygon intersection

• https://www.sciencedirect.com/science/article/abs/pii/0146664X82900235?via%3Dihub
• https://www.geeksforgeeks.org/geometric-algorithms/
• https://github.com/w8r/orourke-compc/blob/master/convconv/convconv.c
• http://cs.smith.edu/~jorourke/books/compgeom.html
• http://www.geom.uiuc.edu/software/qhull/html/qhalf.htm
• https://www.sciencedirect.com/science/article/abs/pii/0146664X82900235
• https://stackoverflow.com/questions/13101288/intersection-of-two-convex-polygons
• https://link.springer.com/article/10.1007/BF01898355
• https://www.swtestacademy.com/intersection-convex-polygons-algorithm/
• https://www.bowdoin.edu/~ltoma/teaching/cs3250-CompGeom/spring17/Lectures/cg-convexintersection.pdf
• https://rosettacode.org/wiki/Sutherland-Hodgman_polygon_clipping#Julia
• https://github.com/JuliaGeometry/PolygonClipping.jl/blob/master/src/PolygonClipping.jl

More on intersections

• https://apps.dtic.mil/dtic/tr/fulltext/u2/a057560.pdf
• http://www-ljk.imag.fr/membres/Antoine.Girard/Publications/hscc2008b.pdf << Zonotope - HalfSpace 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