{"id":{"repo_id":"mcmaster","oai_identifier":"oai:macsphere.mcmaster.ca:11375/33794"},"canonical_url":"https://search.ndltd.org/etd/mcmaster/oai:macsphere.mcmaster.ca:11375/33794","repository":{"repo_id":"mcmaster","name":"McMaster University","base_url":"https://macsphere.mcmaster.ca/server/oai/request"},"display":{"title":"Discrete Geometry and Optimization Approaches for Zonotopes","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Hao, Mingfei"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Computing and Software","school":null,"contributors":[],"advisors":["Deza, Antoine","Franek, Frantisek"],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026","date_published":"2026","updated_at":"2026-11-18T19:38:13Z","subjects":["Discrete geometry","Zonotope","Minkowski sum","Polytope vertex enumeration","Polytope graph and edge enumeration","Linear optimization","Combinatorial optimization","Combinatorial pruning","Parallel algorithms"],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://doi.org/10.71548/25564"],"render_values":[{"text":"https://doi.org/10.71548/25564","href":"https://doi.org/10.71548/25564","code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/11375/33794","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/11375/33794","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://macsphere.mcmaster.ca/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Amacsphere.mcmaster.ca%3A11375%2F33794","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Deza, Antoine","Franek, Frantisek"]},{"key":"dc:contributor.department","label":"Department","values":["Computing and Software"]},{"key":"dc:creator","label":"Author","values":["Hao, Mingfei"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2026-10-14T14:03:08Z"]},{"key":"dc:date.issued","label":"Date","values":["2026"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Discrete geometry","Zonotope","Minkowski sum","Polytope vertex enumeration","Polytope graph and edge enumeration","Linear optimization","Combinatorial optimization","Combinatorial pruning","Parallel algorithms"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/11375/33794","https://doi.org/10.71548/25564"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Doctor of Philosophy (PhD)"]},{"key":"dc:title","label":"Title","values":["Discrete Geometry and Optimization Approaches for Zonotopes"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"dc:contributor.advisor":["Deza, Antoine","Franek, Frantisek"],"dc:contributor.department":["Computing and Software"],"dc:creator":["Hao, Mingfei"],"dc:date.accessioned":["2026-10-14T14:03:08Z"],"dc:date.issued":["2026"],"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."],"dc:description.degree":["Doctor of Philosophy (PhD)"],"dc:identifier.uri":["https://hdl.handle.net/11375/33794","https://doi.org/10.71548/25564"],"dc:language.iso":["en"],"dc:subject":["Discrete geometry","Zonotope","Minkowski sum","Polytope vertex enumeration","Polytope graph and edge enumeration","Linear optimization","Combinatorial optimization","Combinatorial pruning","Parallel algorithms"],"dc:title":["Discrete Geometry and Optimization Approaches for Zonotopes"],"dc:type":["Thesis"],"others:access_status":["open.access"]},"updated_at":"2026-11-18T19:38:13Z"}