91 Search Results for "Lubiw, Anna"

Volume

LIPIcs, Volume 51

32nd International Symposium on Computational Geometry (SoCG 2016)

SoCG 2016, June 14-18, 2016, Boston, USA

Editors: Sándor Fekete and Anna Lubiw

Document
DOI: 10.4230/LIPIcs.SoCG.2023.49
The Geodesic Edge Center of a Simple Polygon

Authors: Anna Lubiw and Anurag Murty Naredla

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
The geodesic edge center of a polygon is a point c inside the polygon that minimizes the maximum geodesic distance from c to any edge of the polygon, where geodesic distance is the shortest path distance inside the polygon. We give a linear-time algorithm to find a geodesic edge center of a simple polygon. This improves on the previous O(n log n) time algorithm by Lubiw and Naredla [European Symposium on Algorithms, 2021]. The algorithm builds on an algorithm to find the geodesic vertex center of a simple polygon due to Pollack, Sharir, and Rote [Discrete & Computational Geometry, 1989] and an improvement to linear time by Ahn, Barba, Bose, De Carufel, Korman, and Oh [Discrete & Computational Geometry, 2016]. The geodesic edge center can easily be found from the geodesic farthest-edge Voronoi diagram of the polygon. Finding that Voronoi diagram in linear time is an open question, although the geodesic nearest edge Voronoi diagram (the medial axis) can be found in linear time. As a first step of our geodesic edge center algorithm, we give a linear-time algorithm to find the geodesic farthest-edge Voronoi diagram restricted to the polygon boundary.
Cite as

Anna Lubiw and Anurag Murty Naredla. The Geodesic Edge Center of a Simple Polygon. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 49:1-49:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lubiw_et_al:LIPIcs.SoCG.2023.49,
  author =	{Lubiw, Anna and Naredla, Anurag Murty},
  title =	{{The Geodesic Edge Center of a Simple Polygon}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{49:1--49:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.49},
  URN =		{urn:nbn:de:0030-drops-178994},
  doi =		{10.4230/LIPIcs.SoCG.2023.49},
  annote =	{Keywords: geodesic center of polygon, farthest edges, farthest-segment Voronoi diagram}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.3
Hardness of Token Swapping on Trees

Authors: Oswin Aichholzer, Erik D. Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masárová, Mikhail Rudoy, Virginia Vassilevska Williams, and Nicole Wein

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Given a graph where every vertex has exactly one labeled token, how can we most quickly execute a given permutation on the tokens? In (sequential) token swapping, the goal is to use the shortest possible sequence of swaps, each of which exchanges the tokens at the two endpoints of an edge of the graph. In parallel token swapping, the goal is to use the fewest rounds, each of which consists of one or more swaps on the edges of a matching. We prove that both of these problems remain NP-hard when the graph is restricted to be a tree. These token swapping problems have been studied by disparate groups of researchers in discrete mathematics, theoretical computer science, robot motion planning, game theory, and engineering. Previous work establishes NP-completeness on general graphs (for both problems), constant-factor approximation algorithms, and some poly-time exact algorithms for simple graph classes such as cliques, stars, paths, and cycles. Sequential and parallel token swapping on trees were first studied over thirty years ago (as "sorting with a transposition tree") and over twenty-five years ago (as "routing permutations via matchings"), yet their complexities were previously unknown. We also show limitations on approximation of sequential token swapping on trees: we identify a broad class of algorithms that encompass all three known polynomial-time algorithms that achieve the best known approximation factor (which is 2) and show that no such algorithm can achieve an approximation factor less than 2.
Cite as

Oswin Aichholzer, Erik D. Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masárová, Mikhail Rudoy, Virginia Vassilevska Williams, and Nicole Wein. Hardness of Token Swapping on Trees. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 3:1-3:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.ESA.2022.3,
  author =	{Aichholzer, Oswin and Demaine, Erik D. and Korman, Matias and Lubiw, Anna and Lynch, Jayson and Mas\'{a}rov\'{a}, Zuzana and Rudoy, Mikhail and Vassilevska Williams, Virginia and Wein, Nicole},
  title =	{{Hardness of Token Swapping on Trees}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.3},
  URN =		{urn:nbn:de:0030-drops-169413},
  doi =		{10.4230/LIPIcs.ESA.2022.3},
  annote =	{Keywords: Sorting, Token swapping, Trees, NP-hard, Approximation}
}
Document
DOI: 10.4230/DagRep.12.2.17
Computation and Reconfiguration in Low-Dimensional Topological Spaces (Dagstuhl Seminar 22062)

Authors: Maike Buchin, Anna Lubiw, Arnaud de Mesmay, Saul Schleimer, and Florestan Brunck

Published in: Dagstuhl Reports, Volume 12, Issue 2 (2022)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22062 "Computation and Reconfiguration in Low-Dimensional Topological Spaces". The seminar consisted of a small collection of introductory talks, an open problem session, and then the seminar participants worked in small groups on problems on reconfiguration within the context of objects as diverse as elimination trees, morphings, curves on surfaces, translation surfaces and Delaunay triangulations.
Cite as

Maike Buchin, Anna Lubiw, Arnaud de Mesmay, Saul Schleimer, and Florestan Brunck. Computation and Reconfiguration in Low-Dimensional Topological Spaces (Dagstuhl Seminar 22062). In Dagstuhl Reports, Volume 12, Issue 2, pp. 17-66, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{buchin_et_al:DagRep.12.2.17,
  author =	{Buchin, Maike and Lubiw, Anna and de Mesmay, Arnaud and Schleimer, Saul and Brunck, Florestan},
  title =	{{Computation and Reconfiguration in Low-Dimensional Topological Spaces (Dagstuhl Seminar 22062)}},
  pages =	{17--66},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{2},
  editor =	{Buchin, Maike and Lubiw, Anna and de Mesmay, Arnaud and Schleimer, Saul and Brunck, Florestan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.2.17},
  URN =		{urn:nbn:de:0030-drops-169305},
  doi =		{10.4230/DagRep.12.2.17},
  annote =	{Keywords: Geometric Topology, Computational Geometry, Graph Drawing, Reconfiguration, Dagstuhl Seminar}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.17
Distant Representatives for Rectangles in the Plane

Authors: Therese Biedl, Anna Lubiw, Anurag Murty Naredla, Peter Dominik Ralbovsky, and Graeme Stroud

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
The input to the distant representatives problem is a set of n objects in the plane and the goal is to find a representative point from each object while maximizing the distance between the closest pair of points. When the objects are axis-aligned rectangles, we give polynomial time constant-factor approximation algorithms for the L₁, L₂, and L_∞ distance measures. We also prove lower bounds on the approximation factors that can be achieved in polynomial time (unless P = NP).
Cite as

Therese Biedl, Anna Lubiw, Anurag Murty Naredla, Peter Dominik Ralbovsky, and Graeme Stroud. Distant Representatives for Rectangles in the Plane. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 17:1-17:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.ESA.2021.17,
  author =	{Biedl, Therese and Lubiw, Anna and Naredla, Anurag Murty and Ralbovsky, Peter Dominik and Stroud, Graeme},
  title =	{{Distant Representatives for Rectangles in the Plane}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{17:1--17:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.17},
  URN =		{urn:nbn:de:0030-drops-145982},
  doi =		{10.4230/LIPIcs.ESA.2021.17},
  annote =	{Keywords: Distant representatives, blocker shapes, matching, approximation algorithm, APX-hardness}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.65
The Visibility Center of a Simple Polygon

Authors: Anna Lubiw and Anurag Murty Naredla

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
We introduce the visibility center of a set of points inside a polygon - a point c_V such that the maximum geodesic distance from c_V to see any point in the set is minimized. For a simple polygon of n vertices and a set of m points inside it, we give an O((n+m) log (n+m)) time algorithm to find the visibility center. We find the visibility center of all points in a simple polygon in O(n log n) time. Our algorithm reduces the visibility center problem to the problem of finding the geodesic center of a set of half-polygons inside a polygon, which is of independent interest. We give an O((n+k) log (n+k)) time algorithm for this problem, where k is the number of half-polygons.
Cite as

Anna Lubiw and Anurag Murty Naredla. The Visibility Center of a Simple Polygon. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 65:1-65:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lubiw_et_al:LIPIcs.ESA.2021.65,
  author =	{Lubiw, Anna and Naredla, Anurag Murty},
  title =	{{The Visibility Center of a Simple Polygon}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{65:1--65:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.65},
  URN =		{urn:nbn:de:0030-drops-146466},
  doi =		{10.4230/LIPIcs.ESA.2021.65},
  annote =	{Keywords: Visibility, Shortest Paths, Simple Polygons, Facility Location}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.14
Bounded-Angle Minimum Spanning Trees

Authors: Ahmad Biniaz, Prosenjit Bose, Anna Lubiw, and Anil Maheshwari

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
Motivated by the connectivity problem in wireless networks with directional antennas, we study bounded-angle spanning trees. Let P be a set of points in the plane and let α be an angle. An α-ST of P is a spanning tree of the complete Euclidean graph on P with the property that all edges incident to each point p ∈ P lie in a wedge of angle α centered at p. We study the following closely related problems for α = 120 degrees (however, our approximation ratios hold for any α ⩾ 120 degrees). 1) The α-minimum spanning tree problem asks for an α-ST of minimum sum of edge lengths. Among many interesting results, Aschner and Katz (ICALP 2014) proved the NP-hardness of this problem and presented a 6-approximation algorithm. Their algorithm finds an α-ST of length at most 6 times the length of the minimum spanning tree (MST). By adopting a somewhat similar approach and using different proof techniques we improve this ratio to 16/3. 2) To examine what is possible with non-uniform wedge angles, we define an ̅α-ST to be a spanning tree with the property that incident edges to all points lie in wedges of average angle α. We present an algorithm to find an ̅α-ST whose largest edge-length and sum of edge lengths are at most 2 and 1.5 times (respectively) those of the MST. These ratios are better than any achievable when all wedges have angle α. Our algorithm runs in linear time after computing the MST.
Cite as

Ahmad Biniaz, Prosenjit Bose, Anna Lubiw, and Anil Maheshwari. Bounded-Angle Minimum Spanning Trees. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 14:1-14:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{biniaz_et_al:LIPIcs.SWAT.2020.14,
  author =	{Biniaz, Ahmad and Bose, Prosenjit and Lubiw, Anna and Maheshwari, Anil},
  title =	{{Bounded-Angle Minimum Spanning Trees}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{14:1--14:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.14},
  URN =		{urn:nbn:de:0030-drops-122616},
  doi =		{10.4230/LIPIcs.SWAT.2020.14},
  annote =	{Keywords: bounded-angle MST, directional antenna, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.33
Universal Communication, Universal Graphs, and Graph Labeling

Authors: Nathaniel Harms

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
We introduce a communication model called universal SMP, in which Alice and Bob receive a function f belonging to a family ℱ, and inputs x and y. Alice and Bob use shared randomness to send a message to a third party who cannot see f, x, y, or the shared randomness, and must decide f(x,y). Our main application of universal SMP is to relate communication complexity to graph labeling, where the goal is to give a short label to each vertex in a graph, so that adjacency or other functions of two vertices x and y can be determined from the labels ℓ(x), ℓ(y). We give a universal SMP protocol using O(k^2) bits of communication for deciding whether two vertices have distance at most k in distributive lattices (generalizing the k-Hamming Distance problem in communication complexity), and explain how this implies a O(k^2 log n) labeling scheme for deciding dist(x,y) ≤ k on distributive lattices with size n; in contrast, we show that a universal SMP protocol for determining dist(x,y) ≤ 2 in modular lattices (a superset of distributive lattices) has super-constant Ω(n^{1/4}) communication cost. On the other hand, we demonstrate that many graph families known to have efficient adjacency labeling schemes, such as trees, low-arboricity graphs, and planar graphs, admit constant-cost communication protocols for adjacency. Trees also have an O(k) protocol for deciding dist(x,y) ≤ k and planar graphs have an O(1) protocol for dist(x,y) ≤ 2, which implies a new O(log n) labeling scheme for the same problem on planar graphs.
Cite as

Nathaniel Harms. Universal Communication, Universal Graphs, and Graph Labeling. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 33:1-33:27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{harms:LIPIcs.ITCS.2020.33,
  author =	{Harms, Nathaniel},
  title =	{{Universal Communication, Universal Graphs, and Graph Labeling}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{33:1--33:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.33},
  URN =		{urn:nbn:de:0030-drops-117182},
  doi =		{10.4230/LIPIcs.ITCS.2020.33},
  annote =	{Keywords: Universal graphs, graph labeling, distance labeling, planar graphs, lattices, hamming distance}
}
Document
DOI: 10.4230/DagRep.9.8.84
Computation in Low-Dimensional Geometry and Topology (Dagstuhl Seminar 19352)

Authors: Maarten Löffler, Anna Lubiw, Saul Schleimer, and Erin Moriarty Wolf Chambers

Published in: Dagstuhl Reports, Volume 9, Issue 8 (2020)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 19352 ``Computation in Low-Dimensional Geometry and Topology''. The seminar participants investigated problems in: knot theory, trajectory analysis, algorithmic topology, computational geometry of curves, and graph drawing, with an emphasis on how low-dimensional structures change over time.
Cite as

Maarten Löffler, Anna Lubiw, Saul Schleimer, and Erin Moriarty Wolf Chambers. Computation in Low-Dimensional Geometry and Topology (Dagstuhl Seminar 19352). In Dagstuhl Reports, Volume 9, Issue 8, pp. 84-112, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{loffler_et_al:DagRep.9.8.84,
  author =	{L\"{o}ffler, Maarten and Lubiw, Anna and Schleimer, Saul and Wolf Chambers, Erin Moriarty},
  title =	{{Computation in Low-Dimensional Geometry and Topology (Dagstuhl Seminar 19352)}},
  pages =	{84--112},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{8},
  editor =	{L\"{o}ffler, Maarten and Lubiw, Anna and Schleimer, Saul and Wolf Chambers, Erin Moriarty},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.8.84},
  URN =		{urn:nbn:de:0030-drops-117734},
  doi =		{10.4230/DagRep.9.8.84},
  annote =	{Keywords: Geometric topology, Graph Drawing, Computational Geometry}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.18
Rollercoasters and Caterpillars

Authors: Therese Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka, and Jeffrey Shallit

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
A rollercoaster is a sequence of real numbers for which every maximal contiguous subsequence - increasing or decreasing - has length at least three. By translating this sequence to a set of points in the plane, a rollercoaster can be defined as an x-monotone polygonal path for which every maximal sub-path, with positive- or negative-slope edges, has at least three vertices. Given a sequence of distinct real numbers, the rollercoaster problem asks for a maximum-length (not necessarily contiguous) subsequence that is a rollercoaster. It was conjectured that every sequence of n distinct real numbers contains a rollercoaster of length at least ceil[n/2] for n>7, while the best known lower bound is Omega(n/log n). In this paper we prove this conjecture. Our proof is constructive and implies a linear-time algorithm for computing a rollercoaster of this length. Extending the O(n log n)-time algorithm for computing a longest increasing subsequence, we show how to compute a maximum-length rollercoaster within the same time bound. A maximum-length rollercoaster in a permutation of {1,...,n} can be computed in O(n log log n) time. The search for rollercoasters was motivated by orthogeodesic point-set embedding of caterpillars. A caterpillar is a tree such that deleting the leaves gives a path, called the spine. A top-view caterpillar is one of maximum degree 4 such that the two leaves adjacent to each vertex lie on opposite sides of the spine. As an application of our result on rollercoasters, we are able to find a planar drawing of every n-vertex top-view caterpillar on every set of 25/3(n+4) points in the plane, such that each edge is an orthogonal path with one bend. This improves the previous best known upper bound on the number of required points, which is O(n log n). We also show that such a drawing can be obtained in linear time, when the points are given in sorted order.
Cite as

Therese Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka, and Jeffrey Shallit. Rollercoasters and Caterpillars. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 18:1-18:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.ICALP.2018.18,
  author =	{Biedl, Therese and Biniaz, Ahmad and Cummings, Robert and Lubiw, Anna and Manea, Florin and Nowotka, Dirk and Shallit, Jeffrey},
  title =	{{Rollercoasters and Caterpillars}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.18},
  URN =		{urn:nbn:de:0030-drops-90224},
  doi =		{10.4230/LIPIcs.ICALP.2018.18},
  annote =	{Keywords: sequences, alternating runs, patterns in permutations, caterpillars}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.49
A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations

Authors: Anna Lubiw, Zuzana Masárová, and Uli Wagner

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of O(n^7) on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture.
Cite as

Anna Lubiw, Zuzana Masárová, and Uli Wagner. A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 49:1-49:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{lubiw_et_al:LIPIcs.SoCG.2017.49,
  author =	{Lubiw, Anna and Mas\'{a}rov\'{a}, Zuzana and Wagner, Uli},
  title =	{{A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{49:1--49:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.49},
  URN =		{urn:nbn:de:0030-drops-72078},
  doi =		{10.4230/LIPIcs.SoCG.2017.49},
  annote =	{Keywords: triangulations, reconfiguration, flip, constrained triangulations, Delaunay triangulation, shellability, piecewise linear balls}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.23
Fractional Coverings, Greedy Coverings, and Rectifier Networks

Authors: Dmitry Chistikov, Szabolcs Iván, Anna Lubiw, and Jeffrey Shallit

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
A rectifier network is a directed acyclic graph with distinguished sources and sinks; it is said to compute a Boolean matrix M that has a 1 in the entry (i,j) iff there is a path from the j-th source to the i-th sink. The smallest number of edges in a rectifier network that computes M is a classic complexity measure on matrices, which has been studied for more than half a century. We explore two techniques that have hitherto found little to no applications in this theory. They build upon a basic fact that depth-2 rectifier networks are essentially weighted coverings of Boolean matrices with rectangles. Using fractional and greedy coverings (defined in the standard way), we obtain new results in this area. First, we show that all fractional coverings of the so-called full triangular matrix have cost at least n log n. This provides (a fortiori) a new proof of the tight lower bound on its depth-2 complexity (the exact value has been known since 1965, but previous proofs are based on different arguments). Second, we show that the greedy heuristic is instrumental in tightening the upper bound on the depth-2 complexity of the Kneser-Sierpinski (disjointness) matrix. The previous upper bound is O(n^{1.28}), and we improve it to O(n^{1.17}), while the best known lower bound is Omega(n^{1.16}). Third, using fractional coverings, we obtain a form of direct product theorem that gives a lower bound on unbounded-depth complexity of Kronecker (tensor) products of matrices. In this case, the greedy heuristic shows (by an argument due to Lovász) that our result is only a logarithmic factor away from the "full" direct product theorem. Our second and third results constitute progress on open problem 7.3 and resolve, up to a logarithmic factor, open problem 7.5 from a recent book by Jukna and Sergeev (in Foundations and Trends in Theoretical Computer Science (2013)).
Cite as

Dmitry Chistikov, Szabolcs Iván, Anna Lubiw, and Jeffrey Shallit. Fractional Coverings, Greedy Coverings, and Rectifier Networks. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 23:1-23:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chistikov_et_al:LIPIcs.STACS.2017.23,
  author =	{Chistikov, Dmitry and Iv\'{a}n, Szabolcs and Lubiw, Anna and Shallit, Jeffrey},
  title =	{{Fractional Coverings, Greedy Coverings, and Rectifier Networks}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.23},
  URN =		{urn:nbn:de:0030-drops-70107},
  doi =		{10.4230/LIPIcs.STACS.2017.23},
  annote =	{Keywords: rectifier network, OR-circuit, biclique covering, fractional covering, greedy covering}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.SoCG.2016
LIPIcs, Volume 51, SoCG'16, Complete Volume

Authors: Sándor Fekete and Anna Lubiw

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
LIPIcs, Volume 51, SoCG'16, Complete Volume
Cite as

Sándor Fekete and Anna Lubiw. LIPIcs, Volume 51, SoCG'16, Complete Volume. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Proceedings{fekete_et_al:LIPIcs.SoCG.2016,
  title =	{{LIPIcs, Volume 51, SoCG'16, Complete Volume}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016},
  URN =		{urn:nbn:de:0030-drops-60580},
  doi =		{10.4230/LIPIcs.SoCG.2016},
  annote =	{Keywords: Analysis of Algorithms and Problem Complexity, Nonnumerical Algorithms and Problems – Geometrical problems and computations, Discrete Mathematics, Combinatorics, Computer Graphics, Computational Geometry and Object Modeling}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.SoCG.2016.0
Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers, Sponsors

Authors: Sándor Fekete and Anna Lubiw

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers, Sponsors
Cite as

Sándor Fekete and Anna Lubiw. Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers, Sponsors. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 0:i-0:xviii, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2016.0,
  author =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  title =	{{Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers, Sponsors}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{0:i--0:xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.0},
  URN =		{urn:nbn:de:0030-drops-59658},
  doi =		{10.4230/LIPIcs.SoCG.2016.0},
  annote =	{Keywords: Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers, Sponsors}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.SoCG.2016.1
Toward Pervasive Robots (Invited Talk)

Authors: Daniela Rus

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
The digitization of practically everything coupled with the mobile Internet, the automation of knowledge work, and advanced robotics promises a future with democratized use of machines and wide-spread use of robots and customization. However, pervasive use of robots remains a hard problem. Where are the gaps that we need to address in order to advance toward a future where robots are common in the world and they help reliably with physical tasks? What is the role of geometric reasoning along this trajectory? In this talk I will discuss challenges toward pervasive use of robots and recent developments in geometric algorithms for customizing robots. I will focus on a suite of gemetric algorithms for automatically designing, fabricating, and tasking robots using a print-and-fold approach. I will also describe how geometric reasoning can play a role in creating robots more capable of reasoning in the world. By enabling on-demand creation of programmable robots, we can begin to imagine a world with one robot for every physical task.
Cite as

Daniela Rus. Toward Pervasive Robots (Invited Talk). In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, p. 1:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{rus:LIPIcs.SoCG.2016.1,
  author =	{Rus, Daniela},
  title =	{{Toward Pervasive Robots}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.1},
  URN =		{urn:nbn:de:0030-drops-58939},
  doi =		{10.4230/LIPIcs.SoCG.2016.1},
  annote =	{Keywords: rus@csail.mit.edu}
}
  • Refine by Author
  • 17 Lubiw, Anna
  • 4 Wagner, Uli
  • 3 Biedl, Therese
  • 3 Demaine, Erik D.
  • 3 Löffler, Maarten
  • Show More...

  • Refine by Classification
  • 6 Theory of computation → Computational geometry
  • 1 Human-centered computing → Graph drawings
  • 1 Mathematics of computing → Geometric topology
  • 1 Mathematics of computing → Graph coloring
  • 1 Mathematics of computing → Probabilistic algorithms
  • Show More...

  • Refine by Keyword
  • 6 Computational Geometry
  • 4 computational geometry
  • 3 Delaunay triangulation
  • 3 Graph Drawing
  • 3 planar graphs
  • Show More...

  • Refine by Type
  • 90 document
  • 1 volume

  • Refine by Publication Year
  • 75 2016
  • 2 2015
  • 2 2017
  • 2 2020
  • 2 2021
  • Show More...

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
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact