[{"oa_version":"None","month":"08","publication":"Advances in Applied Mathematics","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0196-8858"]},"publist_id":"4505","date_published":"2002-08-01T00:00:00Z","type":"journal_article","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_status":"published","date_created":"2018-12-11T11:57:33Z","article_processing_charge":"No","title":"On the number of corner cuts","intvolume":"        29","_id":"2420","scopus_import":"1","author":[{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568"}],"issue":"2","publisher":"ACM","article_type":"original","page":"152 - 161","quality_controlled":"1","doi":"10.1016/S0196-8858(02)00014-3","day":"01","abstract":[{"text":"A corner cut in dimension d is a finite subset of N0d that can be separated from its complement in N0d by an affine hyperplane disjoint from N0d. Corner cuts were first investigated by Onn and Sturmfels [Adv. Appl. Math. 23 (1999) 29-48], their original motivation stemmed from computational commutative algebra. Let us write (Nd0k)cut for the set of corner cuts of cardinality k; in the computational geometer's terminology, these are the k-sets of N0d. Among other things, Onn and Sturmfels give an upper bound of O(k2d(d-1)/(d+1)) for the size of (Nd0k)cut when the dimension is fixed. In two dimensions, it is known (see [Corteel et al., Adv. Appl. Math. 23 (1) (1999) 49-53]) that #(Nd0k)cut = Θ(k log k). We will see that in general, for any fixed dimension d, the order of magnitude of #(Nd0k)cut is between kd-1 log k and (k log k)d-1. (It has been communicated to me that the same bounds have been found independently by G. Rémond.) In fact, the elements of (Nd0k)cut correspond to the vertices of a certain polytope, and what our proof shows is that the above upper bound holds for the total number of flags of that polytope.","lang":"eng"}],"date_updated":"2023-07-25T11:55:42Z","year":"2002","citation":{"ama":"Wagner U. On the number of corner cuts. <i>Advances in Applied Mathematics</i>. 2002;29(2):152-161. doi:<a href=\"https://doi.org/10.1016/S0196-8858(02)00014-3\">10.1016/S0196-8858(02)00014-3</a>","apa":"Wagner, U. (2002). On the number of corner cuts. <i>Advances in Applied Mathematics</i>. ACM. <a href=\"https://doi.org/10.1016/S0196-8858(02)00014-3\">https://doi.org/10.1016/S0196-8858(02)00014-3</a>","chicago":"Wagner, Uli. “On the Number of Corner Cuts.” <i>Advances in Applied Mathematics</i>. ACM, 2002. <a href=\"https://doi.org/10.1016/S0196-8858(02)00014-3\">https://doi.org/10.1016/S0196-8858(02)00014-3</a>.","ieee":"U. Wagner, “On the number of corner cuts,” <i>Advances in Applied Mathematics</i>, vol. 29, no. 2. ACM, pp. 152–161, 2002.","short":"U. Wagner, Advances in Applied Mathematics 29 (2002) 152–161.","mla":"Wagner, Uli. “On the Number of Corner Cuts.” <i>Advances in Applied Mathematics</i>, vol. 29, no. 2, ACM, 2002, pp. 152–61, doi:<a href=\"https://doi.org/10.1016/S0196-8858(02)00014-3\">10.1016/S0196-8858(02)00014-3</a>.","ista":"Wagner U. 2002. On the number of corner cuts. Advances in Applied Mathematics. 29(2), 152–161."},"acknowledgement":"I first learned about corner cuts in a seminar talk in which Artur Andrzejak\r\npresented the results from [6]. My work was initiated by that presentation and\r\nby the discussions that followed it. I also thank Komei Fukuda, Ingo Schurr, and\r\nEmo Welzl for helpful comments and discussions.","volume":29,"extern":"1"}]