---
_id: '2420'
abstract:
- lang: eng
  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.'
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."
article_processing_charge: No
article_type: original
author:
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
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.
  ista: Wagner U. 2002. On the number of corner cuts. Advances in Applied Mathematics.
    29(2), 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>.
  short: U. Wagner, Advances in Applied Mathematics 29 (2002) 152–161.
date_created: 2018-12-11T11:57:33Z
date_published: 2002-08-01T00:00:00Z
date_updated: 2023-07-25T11:55:42Z
day: '01'
doi: 10.1016/S0196-8858(02)00014-3
extern: '1'
intvolume: '        29'
issue: '2'
language:
- iso: eng
month: '08'
oa_version: None
page: 152 - 161
publication: Advances in Applied Mathematics
publication_identifier:
  issn:
  - 0196-8858
publication_status: published
publisher: ACM
publist_id: '4505'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the number of corner cuts
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 29
year: '2002'
...