{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T13:28:34Z","timestamp":1778678914567,"version":"3.51.4"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,9,23]],"date-time":"2015-09-23T00:00:00Z","timestamp":1442966400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math.Comput.Sci."],"published-print":{"date-parts":[[2015,10]]},"DOI":"10.1007\/s11786-015-0238-9","type":"journal-article","created":{"date-parts":[[2015,9,23]],"date-time":"2015-09-23T13:43:14Z","timestamp":1443015794000},"page":"283-325","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Efficient Geometric Operations on Convex Polyhedra, with an Application to Reachability Analysis of Hybrid Systems"],"prefix":"10.1007","volume":"9","author":[{"given":"Willem","family":"Hagemann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,9,23]]},"reference":[{"key":"238_CR1","doi-asserted-by":"crossref","unstructured":"Althoff, M., Krogh, B.H.: Zonotope bundles for the efficient computation of reachable sets. In: 2011 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC), pp. 6814\u20136821. IEEE (2011)","DOI":"10.1109\/CDC.2011.6160872"},{"issue":"3","key":"238_CR2","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1109\/32.489079","volume":"22","author":"R. Alur","year":"1996","unstructured":"Alur R., Henzinger T.A., Ho P.H.: Automatic symbolic verification of embedded systems. IEEE Trans. Softw. Eng. 22(3), 181\u2013201 (1996)","journal-title":"IEEE Trans. Softw. Eng."},{"key":"238_CR3","doi-asserted-by":"crossref","unstructured":"Bagnara, R., Ricci, E., Zaffanella, E., Hill, P.M.: Possibly not closed convex polyhedra and the Parma Polyhedra Library. In: Hermenegildo, M.V., Puebla, G. (eds.) Static Analysis. Lecture Notes in Computer Science, vol. 2477, pp. 213\u2013229. Springer, Berlin (2002)","DOI":"10.1007\/3-540-45789-5_17"},{"key":"238_CR4","doi-asserted-by":"crossref","unstructured":"Bastoul, C.: Code generation in the polyhedral model is easier than you think. In: Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, pp. 7\u201316. IEEE Computer Society (2004)","DOI":"10.1109\/PACT.2004.1342537"},{"issue":"1\u20132","key":"238_CR5","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1017\/S1471068404002261","volume":"5","author":"F. Benoy","year":"2005","unstructured":"Benoy F., King A., Mesnard F.: Computing convex hulls with a linear solver. Theory Pract. Log. Program. 5(1\u20132), 259\u2013271 (2005)","journal-title":"Theory Pract. Log. Program."},{"issue":"1","key":"238_CR6","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/s10479-010-0690-5","volume":"188","author":"E. Boros","year":"2011","unstructured":"Boros E., Elbassioni K., Gurvich V., Tiwary H.R.: The negative cycles polyhedron and hardness of checking some polyhedral properties. Ann. Oper. Res. 188(1), 63\u201376 (2011)","journal-title":"Ann. Oper. Res."},{"key":"238_CR7","doi-asserted-by":"crossref","unstructured":"Chen, X., \u00c1brah\u00e1m, E., Sankaranarayanan, S.: Flow*: An analyzer for non-linear hybrid systems. In: Sharygina, N., Veith, H. (eds.) Computer Aided Verification, Lecture Notes in Computer Science, vol. 8044, pp. 258\u2013263. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-39799-8_18"},{"key":"238_CR8","doi-asserted-by":"crossref","unstructured":"Chutinan, A., Krogh, B.H.: Computing polyhedral approximations to flow pipes for dynamic systems. In: Proceedings of the 37th IEEE Conference on Decision and Control, 1998. vol. 2, pp. 2089\u20132094 (1998)","DOI":"10.1109\/CDC.1998.758642"},{"key":"238_CR9","doi-asserted-by":"crossref","unstructured":"Cousot, P., Halbwachs, N.: Automatic discovery of linear restraints among variables of a program. In: Proceedings of the 5th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, pp. 84\u201396. ACM (1978)","DOI":"10.1145\/512760.512770"},{"issue":"10\u201311","key":"238_CR10","doi-asserted-by":"crossref","first-page":"1122","DOI":"10.1016\/j.scico.2011.07.006","volume":"77","author":"W. Damm","year":"2012","unstructured":"Damm W., Dierks H., Disch S., Hagemann W., Pigorsch F., Scholl C., Waldmann U., Wirtz B.: Exact and fully symbolic verification of linear hybrid automata with large discrete state spaces. Sci. Comput. Program. 77(10\u201311), 1122\u20131150 (2012)","journal-title":"Sci. Comput. Program."},{"key":"238_CR11","unstructured":"Damm, W., Hagemann, W., M\u00f6hlmann, E., Rakow, A.: Component based design of hybrid systems: a case study on concurrency and coupling. Technical Report 95, SFB\/TR 14 AVACS (2014). ISSN: 1860-9821. http:\/\/www.avacs.org"},{"key":"238_CR12","doi-asserted-by":"crossref","unstructured":"Damm, W., M\u00f6hlmann, E., Rakow, A.: Component based design of hybrid systems: a case study on concurrency and coupling. In: Proceedings of the 17th International Conference on Hybrid Systems: Computation and Control, pp. 145\u2013150. HSCC \u201914, ACM, New York (2014)","DOI":"10.1145\/2562059.2562120"},{"key":"238_CR13","unstructured":"Dantzig, G.B.: Linear programming: the story about how it began. In: History of Mathematical Programming, pp. 19\u201331 (1991)"},{"issue":"1","key":"238_CR14","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1287\/opre.8.1.101","volume":"8","author":"G.B. Dantzig","year":"1960","unstructured":"Dantzig G.B., Wolfe P.: Decomposition principle for linear programs. Oper. Res. 8(1), 101\u2013111 (1960)","journal-title":"Oper. Res."},{"key":"238_CR15","doi-asserted-by":"crossref","unstructured":"Frehse, G., Kateja, R., Le Guernic, C.: Flowpipe approximation and clustering in space-time. In: Proceedings of the 16th International Conference on Hybrid Systems: Computation and Control, pp. 203\u2013212. HSCC \u201913, ACM, New York (2013)","DOI":"10.1145\/2461328.2461361"},{"key":"238_CR16","doi-asserted-by":"crossref","unstructured":"Frehse, G., Le Guernic, C., Donz\u00e9, A., Cotton, S., Ray, R., Lebeltel, O., Ripado, R., Girard, A., Dang, T., Maler, O.: SpaceEx: Scalable verification of hybrid systems. In: Gopalakrishnan, G., Qadeer, S. (eds.) Computer Aided Verification. Lecture Notes in Computer Science, vol. 6806, pp. 379\u2013395. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-22110-1_30"},{"key":"238_CR17","unstructured":"Fukuda, K.: Lecture: Polyhedral Computation, Spring 2011 (2011). http:\/\/stat.ethz.ch\/ifor\/teaching\/lectures\/poly_comp_ss11\/lecture_notes"},{"key":"238_CR18","doi-asserted-by":"crossref","unstructured":"Girard, A.: Reachability of uncertain linear systems using zonotopes. In: Morari, M., Thiele, L. (eds.) Hybrid Systems: Computation and Control. Lecture Notes in Computer Science, vol. 3414, pp. 291\u2013305. Springer, Heidelberg (2005)","DOI":"10.1007\/978-3-540-31954-2_19"},{"key":"238_CR19","doi-asserted-by":"crossref","unstructured":"Hagemann, W.: Reachability analysis of hybrid systems using symbolic orthogonal projections. In: Biere, A., Bloem, R. (eds.) Computer Aided Verification. Lecture Notes in Computer Science, vol. 8559, pp. 406\u2013422. Springer International Publishing, Switzerland (2014)","DOI":"10.1007\/978-3-319-08867-9_27"},{"key":"238_CR20","doi-asserted-by":"crossref","unstructured":"Henzinger, T.A., Preussig, J., Wong-Toi, H.: Some lessons from the hytech experience. In: Proceedings of the 40th IEEE Conference on Decision and Control, 2001, vol. 3, pp. 2887\u20132892. IEEE (2001)","DOI":"10.1109\/CDC.2001.980714"},{"issue":"1\u20133","key":"238_CR21","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1007\/s00454-008-9050-5","volume":"39","author":"L. Khachiyan","year":"2008","unstructured":"Khachiyan L., Boros E., Borys K., Elbassioni K., Gurvich V.: Generating all vertices of a polyhedron is hard. Discrete Comput. Geom. 39(1\u20133), 174\u2013190 (2008)","journal-title":"Discrete Comput. Geom."},{"key":"238_CR22","doi-asserted-by":"crossref","unstructured":"Lassez, J.L.: Querying constraints. In: Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 288\u2013298. ACM (1990)","DOI":"10.1145\/298514.298581"},{"key":"238_CR23","unstructured":"Le Guernic, C.: Reachability analysis of hybrid systems with linear continuous dynamics. Ph.D. thesis, Universit\u00e9 Grenoble 1-Joseph Fourier (2009)"},{"key":"238_CR24","doi-asserted-by":"crossref","unstructured":"Le Guernic C., Girard, A.: Reachability analysis of hybrid systems using support functions. In: Bouajjani, A., Maler, O. (eds.) Computer Aided Verification. Lecture Notes in Computer Science, vol. 5643, pp. 540\u2013554. Springer, Heidelberg (2009)","DOI":"10.1007\/978-3-642-02658-4_40"},{"key":"238_CR25","first-page":"51","volume-title":"Contributions to the Theory of Games, vol. 2","author":"T.S. Motzkin","year":"1953","unstructured":"Motzkin T.S., Raiffa H., Thompson G.L., Thrall R.M.: The double description method. In: Kuhn, H.W., Tucker, A.W. Contributions to the Theory of Games, vol. 2, pp. 51\u201373. Princeton University Press, Princeton (1953)"},{"key":"238_CR26","volume-title":"Variational Analysis. Grundlehren der mathematischen Wissenschaften, vol. 317","author":"R.T. Rockafellar","year":"1998","unstructured":"Rockafellar R.T., Wets R.J.B.: Variational Analysis. Grundlehren der mathematischen Wissenschaften, vol. 317. Springer, Berlin (1998)"},{"key":"238_CR27","doi-asserted-by":"crossref","unstructured":"Sankaranarayanan, S., Col\u00f3n, M.A., Sipma, H., Manna, Z.: Efficient strongly relational polyhedral analysis. In: Emerson, E.A., Namjoshi, K.S. (eds.) Verification, Model Checking, and Abstract Interpretation. Lecture Notes in Computer Science, vol. 3855, pp. 111\u2013125. Springer, Heidelberg (2006)","DOI":"10.1007\/11609773_8"},{"key":"238_CR28","doi-asserted-by":"crossref","unstructured":"Sankaranarayanan, S., Dang, T., Ivan\u010di\u0107, F.: Symbolic model checking of hybrid systems using template polyhedra. In: Ramakrishnan, C.R., Rehof, J. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science, vol. 4963, pp. 188\u2013202. Springer, Heidelberg (2008)","DOI":"10.1007\/978-3-540-78800-3_14"},{"key":"238_CR29","volume-title":"Theory of Linear and Integer Programming","author":"A. Schrijver","year":"1986","unstructured":"Schrijver A.: Theory of Linear and Integer Programming. Wiley, New York (1986)"},{"key":"238_CR30","unstructured":"Tebboth, J.R.: A Computational Study of Dantzig\u2013Wolfe Decomposition. Ph.D. thesis, University of Buckingham (2001)"},{"issue":"3","key":"238_CR31","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1007\/s00454-008-9097-3","volume":"40","author":"H.R. Tiwary","year":"2008","unstructured":"Tiwary H.R.: On the hardness of computing intersection, union and Minkowski sum of polytopes. Discrete Comput. Geom. 40(3), 469\u2013479 (2008)","journal-title":"Discrete Comput. Geom."},{"key":"238_CR32","unstructured":"Yan, C.: Projectagon-Based Reachability Analysis for Circuit-Level Formal Verification. Ph.D. thesis, University of British Columbia, Vancouver (2011)"},{"key":"238_CR33","volume-title":"Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152","author":"G.M. Ziegler","year":"1995","unstructured":"Ziegler G.M..: Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer, Berlin (1995)"}],"container-title":["Mathematics in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-015-0238-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11786-015-0238-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-015-0238-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T22:35:11Z","timestamp":1559428511000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11786-015-0238-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,23]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["238"],"URL":"https:\/\/doi.org\/10.1007\/s11786-015-0238-9","relation":{},"ISSN":["1661-8270","1661-8289"],"issn-type":[{"value":"1661-8270","type":"print"},{"value":"1661-8289","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,23]]}}}