Back to search

McMaster University

Discrete Geometry and Optimization Approaches for Zonotopes

Abstract

dc:description.abstract

We consider the problem of generating the vertices of a zonotope, that is, a Minkowski sum of a finite set of segments. We propose a computational, convex-hull-free framework that exploits the combinatorial structure of a zonotope, such as its symmetry group, to generate all canonical representatives of its vertices orbitwise. The thesis further develops the algorithmic and computational architecture required to make this enumeration practical, including combinatorial pruning rules, bit-level generator encodings, parallel enumeration schemes, checkpoint-and-resume recovery, and edge-recovery procedures from archived output. We illustrate the framework by generating the previously intractable 1 955 230 985 997 140 vertices of the 9-dimensional White Whale. We also compute the number of edges of this zonotope up to dimension 9 and exhibit a family of vertices whose degree is exponential in the dimension. The d-dimensional White Whale is the Minkowski sum of all the 2^d − 1 nonzero 0/1-valued vectors in R^d. The central hyperplane arrangement dual to the White Whale, consisting of the hyperplanes normal to these vectors, is the resonance arrangement, which has been studied in various contexts, including algebraic geometry, mathematical physics, economics, psychometrics, and representation theory.

Degree

thesis:*
Department dc:contributor.department
Computing and Software
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hao, Mingfei
Advisors dc:contributor.advisor
  • Deza, Antoine
  • Franek, Frantisek

Subjects

dc:subject × 9

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Hao, Mingfei. Discrete Geometry and Optimization Approaches for Zonotopes. 2026. https://hdl.handle.net/11375/33794