Constructing, Counting and Matching Combinatorial and Geometric Shapes

A shape can be defined as the representation of an object or its external boundary so as to characterize the information remaining when describing an object absent manipulations such as translation, rotation, reflection, or scaling. This includes combinatorial shapes, such as for structures defined in terms of relationships such as "parent-child", "sibling", or "predecessor-successor", as well as geometric shapes, such as those defined by polygons or polytopes. In this thesis, we provide novel methods for constructing, counting, and matching combinatorial and geometric shapes. For example, we study learning and constructing phylogenetic trees, which describe evolutionary relationships among a group of objects. Reconstructing phylogenetic trees is an important problem in computational biology, data protection and computer security. With respect to counting, we focus on characterizing the growth in the number of polycubes and families of polycubes, where a polycube is the shape defined by a connected set of $n$ copies of $d$-dimensional hypercubes. Counting polycubes of a given size has been long-studied in statistical physics, given their applications to percolation processes. We also consider constructing knight’s tour shapes, for chess board grids, optimizing two new metrics of ``simplicity'' in knight’s tours: the number of turns and the number of crossings. Finally, we focus on matching geometric shapes to real-world objects. In particular, motivated by the tracing of ethically-sourced diamonds, we develop approximation algorithms for geometric polyhedral point-set pattern matching as a minimum width polyhedral annulus problem under translations and rotations