LIVIVO - The Search Portal for Life Sciences

zur deutschen Oberfläche wechseln
Advanced search

Search results

Result 1 - 10 of total 24

Search options

  1. Book ; Online: Forbidding Edges between Points in the Plane to Disconnect the Triangulation Flip Graph

    Bigdeli, Reza / Lubiw, Anna

    2022  

    Abstract: The flip graph for a set $P$ of points in the plane has a vertex for every triangulation of $P$, and an edge when two triangulations differ by one flip that replaces one triangulation edge by another. The flip graph is known to have some connectivity ... ...

    Abstract The flip graph for a set $P$ of points in the plane has a vertex for every triangulation of $P$, and an edge when two triangulations differ by one flip that replaces one triangulation edge by another. The flip graph is known to have some connectivity properties: (1) the flip graph is connected; (2) connectivity still holds when restricted to triangulations containing some constrained edges between the points; (3) for $P$ in general position of size $n$, the flip graph is $\lceil \frac{n}{2} -2 \rceil$-connected, a recent result of Wagner and Welzl (SODA 2020). We introduce the study of connectivity properties of the flip graph when some edges between points are forbidden. An edge $e$ between two points is a flip cut edge if eliminating triangulations containing $e$ results in a disconnected flip graph. More generally, a set $X$ of edges between points of $P$ is a flip cut set if eliminating all triangulations that contain edges of $X$ results in a disconnected flip graph. The flip cut number of $P$ is the minimum size of a flip cut set. We give a characterization of flip cut edges that leads to an $O(n \log n)$ time algorithm to test if an edge is a flip cut edge and, with that as preprocessing, an $O(n)$ time algorithm to test if two triangulations are in the same connected component of the flip graph. For a set of $n$ points in convex position (whose flip graph is the 1-skeleton of the associahedron) we prove that the flip cut number is $n-3$.
    Keywords Computer Science - Computational Geometry
    Subject code 511
    Publishing date 2022-06-06
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  2. Book ; Online: The Visibility Center of a Simple Polygon

    Lubiw, Anna / Naredla, Anurag Murty

    2021  

    Abstract: We introduce the \emph{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 ... ...

    Abstract We introduce the \emph{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 \emph{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.

    Comment: Full-length version of a paper that appeared at the European Symposium of Algorithms 2021
    Keywords Computer Science - Computational Geometry
    Publishing date 2021-08-16
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  3. Book ; Online: Building a larger class of graphs for efficient reconfiguration of vertex colouring

    Biedl, Therese / Lubiw, Anna / Merkel, Owen

    2020  

    Abstract: A $k$-colouring of a graph $G$ is an assignment of at most $k$ colours to the vertices of $G$ so that adjacent vertices are assigned different colours. The reconfiguration graph of the $k$-colourings, $\mathcal{R}_k(G)$, is the graph whose vertices are ... ...

    Abstract A $k$-colouring of a graph $G$ is an assignment of at most $k$ colours to the vertices of $G$ so that adjacent vertices are assigned different colours. The reconfiguration graph of the $k$-colourings, $\mathcal{R}_k(G)$, is the graph whose vertices are the $k$-colourings of $G$ and two colourings are joined by an edge in $\mathcal{R}_k(G)$ if they differ in colour on exactly one vertex. For a $k$-colourable graph $G$, we investigate the connectivity and diameter of $\mathcal{R}_{k+1}(G)$. It is known that not all weakly chordal graphs have the property that $\mathcal{R}_{k+1}(G)$ is connected. On the other hand, $\mathcal{R}_{k+1}(G)$ is connected and of diameter $O(n^2)$ for several subclasses of weakly chordal graphs such as chordal, chordal bipartite, and $P_4$-free graphs. We introduce a new class of graphs called OAT graphs that extends the latter classes and in fact extends outside the class of weakly chordal graphs. OAT graphs are built from four simple operations, disjoint union, join, and the addition of a clique or comparable vertex. We prove that if $G$ is a $k$-colourable OAT graph then $\mathcal{R}_{k+1}(G)$ is connected with diameter $O(n^2)$. Furthermore, we give polynomial time algorithms to recognize OAT graphs and to find a path between any two colourings in $\mathcal{R}_{k+1}(G)$.

    Comment: 24 pages, 8 figures
    Keywords Computer Science - Discrete Mathematics
    Subject code 511
    Publishing date 2020-03-03
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  4. Book ; Online: Minimum Ply Covering of Points with Disks and Squares

    Biedl, Therese / Biniaz, Ahmad / Lubiw, Anna

    2019  

    Abstract: Following the seminal work of Erlebach and van Leeuwen in SODA 2008, we introduce the minimum ply covering problem. Given a set $P$ of points and a set $S$ of geometric objects, both in the plane, our goal is to find a subset $S'$ of $S$ that covers all ... ...

    Abstract Following the seminal work of Erlebach and van Leeuwen in SODA 2008, we introduce the minimum ply covering problem. Given a set $P$ of points and a set $S$ of geometric objects, both in the plane, our goal is to find a subset $S'$ of $S$ that covers all points of $P$ while minimizing the maximum number of objects covering any point in the plane (not only points of $P$). For objects that are unit squares and unit disks, this problem is NP-hard and cannot be approximated by a ratio smaller than 2. We present 2-approximation algorithms for this problem with respect to unit squares and unit disks. Our algorithms run in polynomial time when the optimum objective value is bounded by a constant. Motivated by channel-assignment in wireless networks, we consider a variant of the problem where the selected unit disks must be 3-colorable, i.e., colored by three colors such that all disks of the same color are pairwise disjoint. We present a polynomial-time algorithm that achieves a 2-approximate solution, i.e., a solution that is 6-colorable. We also study the weighted version of the problem in dimension one, where $P$ and $S$ are points and weighted intervals on a line, respectively. We present an algorithm that solves this problem in $O(n + m + M )$-time where $n$ is the number of points, $m$ is the number of intervals, and $M$ is the number of pairs of overlapping intervals. This repairs a solution claimed by Nandy, Pandit, and Roy in CCCG 2017.

    Comment: 15 pages
    Keywords Computer Science - Computational Geometry
    Subject code 511
    Publishing date 2019-05-02
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  5. Book ; Online: Distant Representatives for Rectangles in the Plane

    Biedl, Therese / Lubiw, Anna / Naredla, Anurag Murty / Ralbovsky, Peter Dominik / Stroud, Graeme

    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 ... ...

    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_1$, $L_2$, and $L_\infty$ distance measures. We also prove lower bounds on the approximation factors that can be achieved in polynomial time (unless P = NP).

    Comment: Full-length version of a paper to appear at ESA'21
    Keywords Computer Science - Computational Geometry
    Publishing date 2021-08-17
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  6. Book ; Online: Reconstructing a Polyhedron between Polygons in Parallel Slices

    Biedl, Therese / Bulatovic, Pavle / Irvine, Veronika / Lubiw, Anna / Merkel, Owen / Naredla, Anurag Murty

    2020  

    Abstract: Given two $n$-vertex polygons, $P=(p_1, \ldots, p_n)$ lying in the $xy$-plane at $z=0$, and $P'=(p'_1, \ldots, p'_n)$ lying in the $xy$-plane at $z=1$, a banded surface is a triangulated surface homeomorphic to an annulus connecting $P$ and $P'$ such ... ...

    Abstract Given two $n$-vertex polygons, $P=(p_1, \ldots, p_n)$ lying in the $xy$-plane at $z=0$, and $P'=(p'_1, \ldots, p'_n)$ lying in the $xy$-plane at $z=1$, a banded surface is a triangulated surface homeomorphic to an annulus connecting $P$ and $P'$ such that the triangulation's edge set contains vertex disjoint paths $\pi_i$ connecting $p_i$ to $p'_i$ for all $i =1, \ldots, n$. The surface then consists of bands, where the $i$th band goes between $\pi_i$ and $\pi_{i+1}$. We give a polynomial-time algorithm to find a banded surface without Steiner points if one exists. We explore connections between banded surfaces and linear morphs, where time in the morph corresponds to the $z$ direction. In particular, we show that if $P$ and $P'$ are convex and the linear morph from $P$ to $P'$ (which moves the $i$th vertex on a straight line from $p_i$ to $p'_i$) remains planar at all times, then there is a banded surface without Steiner points.

    Comment: preliminary version appeared in the Canadian Conference on Computational Geometry (CCCG) 2019
    Keywords Computer Science - Computational Geometry ; 05C10 ; 52C99 ; 68W99 ; F.2.2 ; G.2.2
    Subject code 516 ; 511
    Publishing date 2020-04-13
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  7. Book ; Online: Hardness of Token Swapping on Trees

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

    2021  

    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 ... ...

    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); polynomial-time algorithms for simple graph classes such as cliques, stars, paths, and cycles; and constant-factor approximation algorithms in some cases. The two natural cases of sequential and parallel token swapping in 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$.
    Keywords Computer Science - Data Structures and Algorithms ; Computer Science - Computational Complexity
    Subject code 511
    Publishing date 2021-03-11
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  8. Book ; Online: Shortest Paths and Convex Hulls in 2D Complexes with Non-Positive Curvature

    Lubiw, Anna / Maftuleac, Daniela / Owen, Megan

    2016  

    Abstract: Globally non-positively curved, or CAT(0), polyhedral complexes arise in a number of applications, including evolutionary biology and robotics. These spaces have unique shortest paths and are composed of Euclidean polyhedra, yet many algorithms and ... ...

    Abstract Globally non-positively curved, or CAT(0), polyhedral complexes arise in a number of applications, including evolutionary biology and robotics. These spaces have unique shortest paths and are composed of Euclidean polyhedra, yet many algorithms and properties of shortest paths and convex hulls in Euclidean space fail to transfer over. We give an algorithm, using linear programming, to compute the convex hull of a set of points in a 2-dimensional CAT(0) polyhedral complex with a single vertex. We explore the use of shortest path maps to answer single-source shortest path queries in 2-dimensional CAT(0) polyhedral complexes, and we unify efficient solutions for 2-manifold and rectangular cases.

    Comment: minor clarifications
    Keywords Computer Science - Computational Geometry ; Mathematics - Combinatorics ; Mathematics - Metric Geometry
    Publishing date 2016-03-02
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  9. Book ; Online: Maximum Matchings and Minimum Blocking Sets in $\Theta_6$-Graphs

    Biedl, Therese / Biniaz, Ahmad / Irvine, Veronika / Jain, Kshitij / Kindermann, Philipp / Lubiw, Anna

    2019  

    Abstract: Theta_6$-Graphs graphs are important geometric graphs that have many applications especially in wireless sensor networks. They are equivalent to Delaunay graphs where empty equilateral triangles take the place of empty circles. We investigate lower ... ...

    Abstract $\Theta_6$-Graphs graphs are important geometric graphs that have many applications especially in wireless sensor networks. They are equivalent to Delaunay graphs where empty equilateral triangles take the place of empty circles. We investigate lower bounds on the size of maximum matchings in these graphs. The best known lower bound is $n/3$, where $n$ is the number of vertices of the graph. Babu et al. (2014) conjectured that any $\Theta_6$-graph has a (near-)perfect matching (as is true for standard Delaunay graphs). Although this conjecture remains open, we improve the lower bound to $(3n-8)/7$. We also relate the size of maximum matchings in $\Theta_6$-graphs to the minimum size of a blocking set. Every edge of a $\Theta_6$-graph on point set $P$ corresponds to an empty triangle that contains the endpoints of the edge but no other point of $P$. A blocking set has at least one point in each such triangle. We prove that the size of a maximum matching is at least $\beta(n)/2$ where $\beta(n)$ is the minimum, over all theta-six graphs with $n$ vertices, of the minimum size of a blocking set. In the other direction, lower bounds on matchings can be used to prove bounds on $\beta$, allowing us to show that $\beta(n)\geq 3n/4-2$.
    Keywords Computer Science - Computational Geometry
    Subject code 511
    Publishing date 2019-01-05
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

  10. Book ; Online: Face flips in origami tessellations

    Akitaya, Hugo A. / Dujmovi, Vida / Eppstein, David / Hull, Thomas C. / Jain, Kshitij / Lubiw, Anna

    2019  

    Abstract: Given a flat-foldable origami crease pattern $G=(V,E)$ (a straight-line drawing of a planar graph on a region of the plane) with a mountain-valley (MV) assignment $\mu:E\to\{-1,1\}$ indicating which creases in $E$ bend convexly (mountain) or concavely ( ... ...

    Abstract Given a flat-foldable origami crease pattern $G=(V,E)$ (a straight-line drawing of a planar graph on a region of the plane) with a mountain-valley (MV) assignment $\mu:E\to\{-1,1\}$ indicating which creases in $E$ bend convexly (mountain) or concavely (valley), we may \emph{flip} a face $F$ of $G$ to create a new MV assignment $\mu_F$ which equals $\mu$ except for all creases $e$ bordering $F$, where we have $\mu_F(e)=-\mu(e)$. In this paper we explore the configuration space of face flips for a variety of crease patterns $G$ that are tilings of the plane, proving examples where $\mu_F$ results in a MV assignment that is either never, sometimes, or always flat-foldable for various choices of $F$. We also consider the problem of finding, given two foldable MV assignments $\mu_1$ and $\mu_2$ of a given crease pattern $G$, a minimal sequence of face flips to turn $\mu_1$ into $\mu_2$. We find polynomial-time algorithms for this in the cases where $G$ is either a square grid or the Miura-ori, and show that this problem is NP-hard in the case where $G$ is the triangle lattice.
    Keywords Mathematics - Combinatorics ; Computer Science - Computational Geometry ; 52C45 ; 68U05
    Subject code 511
    Publishing date 2019-10-12
    Publishing country us
    Document type Book ; Online
    Database BASE - Bielefeld Academic Search Engine (life sciences selection)

    Full text online

    More links

    Kategorien

    Inter-library loan at ZB MED

    Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

To top