{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T22:42:57Z","timestamp":1790808177162,"version":"4.1.0"},"reference-count":10,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"name":"University of Economics, Prague V\u00cbSE","award":["IP100040"],"award-info":[{"award-number":["IP100040"]}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura Cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["P403\/16-00408S"],"award-info":[{"award-number":["P403\/16-00408S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We design a new algorithm, called Incremental Enumeration (IncEnu), for the enumeration of full-dimensional cells of hyperplane arrangements (or dually, for the enumeration of vertices of generator-presented zonotopes). The algorithm is based on an incremental construction of the graph of cells of the arrangement. IncEnu is compared to Avis and Fukuda's Reverse Search (RS), including its later improvements by Sleumer and others. The basic versions of IncEnu and RS are not directly comparable, since they solve different numbers of linear programs (LPs) of different sizes. We therefore reformulate our algorithm as a version that permits comparison with RS in terms of the number of LPs solved. The result is that both IncEnu and RS have \u201cthe same\u201d complexity-theoretic properties (compactness, output-polynomiality, worst-case bounds, tightness of bounds). In spite of the fact that IncEnu and RS have the same asymptotic bounds, it is proved that IncEnu is faster than RS by a nontrivial additive term. Our computational experiments show that for most test cases IncEnu is significantly faster than RS in practice. Based on the results obtained, we conjecture that IncEnu is $\\mathcal{O}(d)$ times faster for nondegenerate arrangements, where $d$ denotes the dimension of the arrangement.<\/jats:p>","DOI":"10.1137\/15m1027930","type":"journal-article","created":{"date-parts":[[2018,2,13]],"date-time":"2018-02-13T14:07:21Z","timestamp":1518530841000},"page":"455-473","source":"Crossref","is-referenced-by-count":19,"title":["A New Algorithm for Enumeration of Cells of Hyperplane Arrangements and a Comparison with Avis and Fukuda's Reverse Search"],"prefix":"10.1137","volume":"32","author":[{"given":"Miroslav","family":"Rada","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michal","family":"\u010cern\u00fd","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,2,13]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100233"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00026-N"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1943.11991447"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(98)00021-2"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/0215024"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2003.04.011"},{"key":"atypb7","unstructured":"Gurobi Optimizer Reference Manual\n                      , Gurobi Optimization, Inc., Houston, TX, 2014."},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"Tm. Ottmann, S. Schuierer, and S. Soundaralakshmi,\n                      Enumerating extreme points in higher dimensions\n                      , in STACS 95: 12th Animal Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 900, Springer, Berlin, 1995, pp. 562-570,doi:10.1007\/3-540-59042-0_105.","DOI":"10.1007\/3-540-59042-0_105"},{"key":"atypb9","first-page":"300","author":"Sleumer N.","year":"1998","journal-title":"Springer Berlin"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"T. Zaslavsky,\n                      Facing up to Arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes\n                      , Memoirs of the American Mathematical Society 154, American Mathematical Society, Providence, RI 1975.","DOI":"10.1090\/memo\/0154"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1027930","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:54:01Z","timestamp":1787316841000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1027930"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":10,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/15M1027930"],"URL":"https:\/\/doi.org\/10.1137\/15m1027930","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}