2 Search Results for "Hesterberg, Adam C."


Document
Finding Closed Quasigeodesics on Convex Polyhedra

Authors: Erik D. Demaine, Adam C. Hesterberg, and Jason S. Ku

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)


Abstract
A closed quasigeodesic is a closed loop on the surface of a polyhedron with at most 180° of surface on both sides at all points; such loops can be locally unfolded straight. In 1949, Pogorelov proved that every convex polyhedron has at least three (non-self-intersecting) closed quasigeodesics, but the proof relies on a nonconstructive topological argument. We present the first finite algorithm to find a closed quasigeodesic on a given convex polyhedron, which is the first positive progress on a 1990 open problem by O'Rourke and Wyman. The algorithm’s running time is pseudopolynomial, namely O(n²/ε² L/𝓁 b) time, where ε is the minimum curvature of a vertex, L is the length of the longest edge, 𝓁 is the smallest distance within a face between a vertex and a nonincident edge (minimum feature size of any face), and b is the maximum number of bits of an integer in a constant-size radical expression of a real number representing the polyhedron. We take special care in the model of computation and needed precision, showing that we can achieve the stated running time on a pointer machine supporting constant-time w-bit arithmetic operations where w = Ω(lg b).

Cite as

Erik D. Demaine, Adam C. Hesterberg, and Jason S. Ku. Finding Closed Quasigeodesics on Convex Polyhedra. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 33:1-33:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{demaine_et_al:LIPIcs.SoCG.2020.33,
  author =	{Demaine, Erik D. and Hesterberg, Adam C. and Ku, Jason S.},
  title =	{{Finding Closed Quasigeodesics on Convex Polyhedra}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{33:1--33:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.33},
  URN =		{urn:nbn:de:0030-drops-121912},
  doi =		{10.4230/LIPIcs.SoCG.2020.33},
  annote =	{Keywords: polyhedra, geodesic, pseudopolynomial, geometric precision}
}
Document
Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class

Authors: Erik D. Demaine, Timothy D. Goodrich, Kyle Kloster, Brian Lavallee, Quanquan C. Liu, Blair D. Sullivan, Ali Vakilian, and Andrew van der Poel

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)


Abstract
We develop a framework for generalizing approximation algorithms from the structural graph algorithm literature so that they apply to graphs somewhat close to that class (a scenario we expect is common when working with real-world networks) while still guaranteeing approximation ratios. The idea is to edit a given graph via vertex- or edge-deletions to put the graph into an algorithmically tractable class, apply known approximation algorithms for that class, and then lift the solution to apply to the original graph. We give a general characterization of when an optimization problem is amenable to this approach, and show that it includes many well-studied graph problems, such as Independent Set, Vertex Cover, Feedback Vertex Set, Minimum Maximal Matching, Chromatic Number, (l-)Dominating Set, Edge (l-)Dominating Set, and Connected Dominating Set. To enable this framework, we develop new editing algorithms that find the approximately-fewest edits required to bring a given graph into one of a few important graph classes (in some cases these are bicriteria algorithms which simultaneously approximate both the number of editing operations and the target parameter of the family). For bounded degeneracy, we obtain an O(r log{n})-approximation and a bicriteria (4,4)-approximation which also extends to a smoother bicriteria trade-off. For bounded treewidth, we obtain a bicriteria (O(log^{1.5} n), O(sqrt{log w}))-approximation, and for bounded pathwidth, we obtain a bicriteria (O(log^{1.5} n), O(sqrt{log w} * log n))-approximation. For treedepth 2 (related to bounded expansion), we obtain a 4-approximation. We also prove complementary hardness-of-approximation results assuming P != NP: in particular, these problems are all log-factor inapproximable, except the last which is not approximable below some constant factor 2 (assuming UGC).

Cite as

Erik D. Demaine, Timothy D. Goodrich, Kyle Kloster, Brian Lavallee, Quanquan C. Liu, Blair D. Sullivan, Ali Vakilian, and Andrew van der Poel. Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{demaine_et_al:LIPIcs.ESA.2019.37,
  author =	{Demaine, Erik D. and Goodrich, Timothy D. and Kloster, Kyle and Lavallee, Brian and Liu, Quanquan C. and Sullivan, Blair D. and Vakilian, Ali and van der Poel, Andrew},
  title =	{{Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{37:1--37:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.37},
  URN =		{urn:nbn:de:0030-drops-111583},
  doi =		{10.4230/LIPIcs.ESA.2019.37},
  annote =	{Keywords: structural rounding, graph editing, approximation algorithms}
}
  • Refine by Author
  • 2 Demaine, Erik D.
  • 1 Goodrich, Timothy D.
  • 1 Hesterberg, Adam C.
  • 1 Kloster, Kyle
  • 1 Ku, Jason S.
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 approximation algorithms
  • 1 geodesic
  • 1 geometric precision
  • 1 graph editing
  • 1 polyhedra
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2019
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail