<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T16:33:11Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/1037" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/1037</identifier><datestamp>2017-03-21T19:45:11Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" lang="en" authority="8ca15dfe-cef4-4d85-bf2a-18fa02a2d9fc" confidence="600">Lucier, Brendan</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2006-08-22T14:19:50Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2006-08-22T14:19:50Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued" lang="en">2006</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted" lang="en">2006</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/1037</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">This thesis covers work on two topics: unfolding polyhedra into the plane and reconstructing polyhedra from partial information.    For each topic, we describe previous work in the area and present an array of new research and results.       
Our work on unfolding is motivated by the problem of characterizing precisely when overlaps will occur when a polyhedron is cut along edges and unfolded.    By contrast to previous work, we begin by classifying overlaps according to a notion of locality.    This classification enables us to focus upon particular types of overlaps, and use the results to construct examples of polyhedra with interesting unfolding properties.       
The research on unfolding is split into convex and non-convex cases.   In the non-convex case, we construct a polyhedron for which every edge unfolding has an overlap, with fewer faces than all previously known examples.   We also construct a non-convex polyhedron for which every edge unfolding has a particularly trivial type of overlap.    In the convex case, we construct a series of example polyhedra for which every unfolding of various types has an overlap.    These examples disprove some existing conjectures regarding algorithms to unfold convex polyhedra without overlaps.       
The work on reconstruction is centered around analyzing the computational complexity of a number of reconstruction questions.    We consider two classes of reconstruction problems.   The first problem is as follows: given a collection of edges in space, determine whether they can be rearranged &amp;lt;em&amp;gt;by translation only&amp;lt;/em&amp;gt; to form a polygon or polyhedron.   We consider variants of this problem by introducing restrictions like convexity, orthogonality, and non-degeneracy.   All of these problems are NP-complete, though some are proved to be only weakly NP-complete.   We then consider a second, more classical problem: given a collection of edges in space, determine whether they can be rearranged by &amp;lt;em&amp;gt;translation and/or rotation&amp;lt;/em&amp;gt; to form a polygon or polyhedron.   This problem is NP-complete for orthogonal polygons, but polynomial algorithms exist for non-orthogonal polygons.   For polyhedra, it is shown that if degeneracies are allowed then the problem is NP-hard, but the complexity is still unknown for non-degenerate polyhedra.</dim:field>
   <dim:field mdschema="dc" element="format" lang="en">application/pdf</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="extent">1715858 bytes</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="rights" lang="en">Copyright: 2006, 
  Lucier, Brendan. All rights reserved.</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Polyhedra</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Polygons</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Reconstruction</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Unfolding</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Geometry</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Unfolding and Reconstructing Polyhedra</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>