Back to search

University of British Columbia

Polytopes of minimal circuit diameter

Abstract

dc:description

Finding the optimal point in a feasible region, such as an n-dimensional polytope, is foundational to the field of optimization. Circuits, the set of all potential edges of a polyhedron, provide us a way to travel the feasible region in search of optimality. This thesis explores the circuit diameter, a generalization of combinatorial diameter using circuits, of certain polytopes, focusing on when the circuit diameter is small and what criteria for small circuit diameter exist. Such classifications of polytopes with small circuit diameter may indicate when a circuit-based optimization algorithm would be preferred. In this thesis, we use counting arguments and a few general results on circuits to classify when a polytope may have circuit diameter 1. We show that in two dimensions circuits have special properties and there are unique classes of polytope with circuit diameter 1 under affine transformation, which depend on number of vertices. We also provide a way to construct these 1-circuit polygons. We examine polytopes in three dimensions, where the construction and interaction of circuits becomes more complicated. We consider several common classes of 3-dimensional polytopes to determine when we can construct them to have small circuit diameter. We then expand our results to higher dimensions and study some of the generalized polytopes from lower dimensions. We finish with some numerical results of algorithms which calculate circuits of a polytope and generate our 1-circuit polygons.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Mathematics
Grantor dc:publisher
University of British Columbia
Year dc:date
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Yoder, Jeremiah
Contributors dc:contributor
  • Wiebe, Amy

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/93736

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Yoder, Jeremiah. Polytopes of minimal circuit diameter. master's thesis, University of British Columbia, 2026. http://hdl.handle.net/2429/93736