{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/117875"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/117875","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Closed quasigeodesics, escaping from polygons, and conflict-free graph coloring","abstract":"Closed quasigeodesics. A closed quasigeodesic on the surface of a polyhedron is a loop which can everywhere locally be unfolded to a straight line: thus, it's straight on faces, uniquely determined on edges, and has as much flexibility at a vertex as that vertex's curvature. On any polyhedron, at least three closed quasigeodesics are known to exist, by a nonconstructive topological proof. We present an algorithm to find one on any convex polyhedron in time O(n2[epsilon]-2- 2Ll-1 ), where [epsilon] e is the minimum curvature of a vertex, l is the length of the longest side, and t is the smallest distance within a face between a vertex and an edge not containing it. Escaping from polygons. You move continuously at speed 1 in the interior of a polygon P, trying to reach the boundary. A zombie moves continuously at speed r outside P, trying to be at the boundary when you reach it. For what r can you escape and for what r can the zombie catch you? We give exact results for some P. For general P, we give a simple approximation to within a factor of roughly 9.2504. We also give a pseudopolynomial-time approximation scheme. Finally, we prove NP-hardness and hardness of approximation results for related problems with multiple zombies and/or humans. Conflict-free graph coloring. A conflict-free k-coloring of a graph assigns one of k different colors to some of the vertices such that, for every vertex v, there is a color that is assigned to exactly one vertex among v and v's neighbors. We study the natural problem of the conflict-free chromatic number XCF(G) (the smallest k for which conflict-free k-colorings exist), with a focus on planar graphs.","abstract_html":"Closed quasigeodesics. A closed quasigeodesic on the surface of a polyhedron is a loop which can everywhere locally be unfolded to a straight line: thus, it's straight on faces, uniquely determined on edges, and has as much flexibility at a vertex as that vertex's curvature. On any polyhedron, at least three closed quasigeodesics are known to exist, by a nonconstructive topological proof. We present an algorithm to find one on any convex polyhedron in time O(n2[epsilon]-2- 2Ll-1 ), where [epsilon] e is the minimum curvature of a vertex, l is the length of the longest side, and t is the smallest distance within a face between a vertex and an edge not containing it. Escaping from polygons. You move continuously at speed 1 in the interior of a polygon P, trying to reach the boundary. A zombie moves continuously at speed r outside P, trying to be at the boundary when you reach it. For what r can you escape and for what r can the zombie catch you? We give exact results for some P. For general P, we give a simple approximation to within a factor of roughly 9.2504. We also give a pseudopolynomial-time approximation scheme. Finally, we prove NP-hardness and hardness of approximation results for related problems with multiple zombies and/or humans. Conflict-free graph coloring. A conflict-free k-coloring of a graph assigns one of k different colors to some of the vertices such that, for every vertex v, there is a color that is assigned to exactly one vertex among v and v's neighbors. We study the natural problem of the conflict-free chromatic number XCF(G) (the smallest k for which conflict-free k-colorings exist), with a focus on planar graphs.","abstract_has_math":false,"creators":["Hesterberg, Adam Classen"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Mathematics.","school":null,"contributors":[],"advisors":["Erik Demaine."],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018","date_published":"2018","updated_at":"2026-07-22T22:20:51Z","subjects":["Mathematics."],"languages":["eng"],"rights":["MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/117875","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Erik Demaine."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Mathematics."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Department of Mathematics."]},{"key":"dc:creator","label":"Author","values":["Hesterberg, Adam Classen"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2018-09-17T15:48:06Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2018-09-17T15:48:06Z"]},{"key":"dc:date.issued","label":"Date","values":["2018"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/117875"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2018.","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 56-58)."]},{"key":"dc:description.abstract","label":"Abstract","values":["Closed quasigeodesics. A closed quasigeodesic on the surface of a polyhedron is a loop which can everywhere locally be unfolded to a straight line: thus, it's straight on faces, uniquely determined on edges, and has as much flexibility at a vertex as that vertex's curvature. On any polyhedron, at least three closed quasigeodesics are known to exist, by a nonconstructive topological proof. We present an algorithm to find one on any convex polyhedron in time O(n2[epsilon]-2- 2Ll-1 ), where [epsilon] e is the minimum curvature of a vertex, l is the length of the longest side, and t is the smallest distance within a face between a vertex and an edge not containing it. Escaping from polygons. You move continuously at speed 1 in the interior of a polygon P, trying to reach the boundary. A zombie moves continuously at speed r outside P, trying to be at the boundary when you reach it. For what r can you escape and for what r can the zombie catch you? We give exact results for some P. For general P, we give a simple approximation to within a factor of roughly 9.2504. We also give a pseudopolynomial-time approximation scheme. Finally, we prove NP-hardness and hardness of approximation results for related problems with multiple zombies and/or humans. Conflict-free graph coloring. A conflict-free k-coloring of a graph assigns one of k different colors to some of the vertices such that, for every vertex v, there is a color that is assigned to exactly one vertex among v and v's neighbors. We study the natural problem of the conflict-free chromatic number XCF(G) (the smallest k for which conflict-free k-colorings exist), with a focus on planar graphs."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph. D."]},{"key":"dc:title","label":"Title","values":["Closed quasigeodesics, escaping from polygons, and conflict-free graph coloring"]}]}],"canonical_facts":{"dc:contributor.advisor":["Erik Demaine."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Mathematics."],"dc:contributor.other":["Massachusetts Institute of Technology. Department of Mathematics."],"dc:creator":["Hesterberg, Adam Classen"],"dc:date.accessioned":["2018-09-17T15:48:06Z"],"dc:date.available":["2018-09-17T15:48:06Z"],"dc:date.issued":["2018"],"dc:description":["Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2018.","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 56-58)."],"dc:description.abstract":["Closed quasigeodesics. A closed quasigeodesic on the surface of a polyhedron is a loop which can everywhere locally be unfolded to a straight line: thus, it's straight on faces, uniquely determined on edges, and has as much flexibility at a vertex as that vertex's curvature. On any polyhedron, at least three closed quasigeodesics are known to exist, by a nonconstructive topological proof. We present an algorithm to find one on any convex polyhedron in time O(n2[epsilon]-2- 2Ll-1 ), where [epsilon] e is the minimum curvature of a vertex, l is the length of the longest side, and t is the smallest distance within a face between a vertex and an edge not containing it. Escaping from polygons. You move continuously at speed 1 in the interior of a polygon P, trying to reach the boundary. A zombie moves continuously at speed r outside P, trying to be at the boundary when you reach it. For what r can you escape and for what r can the zombie catch you? We give exact results for some P. For general P, we give a simple approximation to within a factor of roughly 9.2504. We also give a pseudopolynomial-time approximation scheme. Finally, we prove NP-hardness and hardness of approximation results for related problems with multiple zombies and/or humans. Conflict-free graph coloring. A conflict-free k-coloring of a graph assigns one of k different colors to some of the vertices such that, for every vertex v, there is a color that is assigned to exactly one vertex among v and v's neighbors. We study the natural problem of the conflict-free chromatic number XCF(G) (the smallest k for which conflict-free k-colorings exist), with a focus on planar graphs."],"dc:description.degree":["Ph. D."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/117875"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Mathematics."],"dc:title":["Closed quasigeodesics, escaping from polygons, and conflict-free graph coloring"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:20:51Z"}