  We study the menu complexity of optimal and approximately-optimal auctions in
the context of the "FedEx" problem, a so-called "one-and-a-half-dimensional"
setting where a single bidder has both a value and a deadline for receiving an
[FGKK16]. The menu complexity of an auction is equal to the number of distinct
(allocation, price) pairs that a bidder might receive [HN13]. We show the
following when the bidder has $n$ possible deadlines:
  - Exponential menu complexity is necessary to be exactly optimal: There exist
instances where the optimal mechanism has menu complexity is $2^n-1$. This
matches exactly the upper bound provided by Fiat et al.'s algorithm, and
resolves one of their open questions [FGKK16].
  - Fully polynomial menu complexity is necessary and sufficient for
approximation: For all instances, there exists a mechanism guaranteeing a
multiplicative (1-\epsilon)-approximation to the optimal revenue with menu
complexity $O(n^{3/2}\sqrt{\frac{\min\{n/\epsilon,\ln(v_{\max})\}}{\epsilon}})
= O(n^2/\epsilon)$, where $v_{\max}$ denotes the largest value in the support
of integral distributions.
  - There exist instances where any mechanism guaranteeing a multiplicative
$(1-O(1/n^2))$-approximation to the optimal revenue requires menu complexity
$\Omega(n^2)$.
  Our main technique is the polygon approximation of concave functions
[Rote19], and our results here should be of independent interest. We further
show how our techniques can be used to resolve an open question of [DW17] on
the menu complexity of optimal auctions for a budget-constrained buyer.
