Submitted Journal Conference Chapters Theses Talks

Currently under review

  1. Flipping in spirals


    Abstract: We study the number of edge flips required to transform any triangulation of a spiral polygon into any other. We improve the upper bound from $4n - 6$ to $3n - 9$ flips and show a lower bound of $2n - 8$ flips. Instead of using a single canonical triangulation as the intermediate point in the transformation between two triangulations, we use a family of closely-connected triangulations.
    Submitted to the 31st Canadian Conference on Computational Geometry (CCCG 2019).

  2. Constrained routing between non-visible vertices


    Abstract:

    In this paper we study local routing strategies on geometric graphs. Such strategies use geometric properties of the graph like the coordinates of the current and target nodes to route. Specifically, we study routing strategies in the presence of constraints which are obstacles that edges of the graph are not allowed to cross. Let $P$ be a set of $n$ points in the plane and let $S$ be a set of line segments whose endpoints are in $P$, with no two line segments intersecting properly. We present the first deterministic 1-local $O(1)$-memory routing algorithm that is guaranteed to find a path between two vertices in the visibility graph of $P$ with respect to a set of constraints $S$. The strategy never looks beyond the direct neighbors of the current node and does not store more than $O(1)$-information to reach the target.

    We then turn our attention to finding competitive routing strategies. We show that when routing on any triangulation $T$ of $P$ such that $S \subseteq T$, no $o(n)$-competitive routing algorithm exists when the routing strategy restricts its attention to the triangles intersected by the line segment from the source to the target (a technique commonly used in the unconstrained setting). Finally, we provide an $O(n)$-competitive deterministic 1-local $O(1)$-memory routing algorithm on any such $T$, which is optimal in the worst case, given the lower bound.

    With P. Bose, M. Korman, and A. van Renssen.
    Submitted to Theoretical Computer Science.
    pdf arXiv Conference version 
    @article{non-visible-constrained-routing-journal,
  author={Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Verdonschot, Sander},
  title={Constrained Routing Between Non-Visible Vertices},
  year={2017},
  journal={ArXiv e-prints},
  archivePrefix={arXiv},
  eprint={1710.08060},
  primaryClass={cs.CG},
  note={\href{http://arxiv.org/abs/1710.08060}{arXiv:1710.08060} [cs.CG]},
  url={http://arxiv.org/abs/1710.08060}
}

Submitted Journal Conference Chapters Theses Talks

Journal papers

  1. On the average number of edges in Theta graphs


    Abstract: Theta graphs are important geometric graphs that have many applications, including wireless networking, motion planning, real-time animation, and minimum-spanning tree construction. We give closed form expressions for the average degree of theta graphs of a homogeneous Poisson point process over the plane. We then show that essentially the same bounds—with vanishing error terms—hold for theta graphs of finite sets of points that are uniformly distributed in a square. Finally, we show that the number of edges in a theta graph of points uniformly distributed in a square is concentrated around its expected value.
    With P. Morin.
    Accepted to Online Journal of Analytic Combinatorics.
    pdf arXiv Conference version Mathematica code 
    @article{morin2014average,
  author={Morin, Pat and Verdonschot, Sander},
  title={On the Average Number of Edges in {T}heta Graphs},
  journal={Online Journal of Analytic Combinatorics},
  year={2014}
}

  2. Improved bounds for guarding plane graphs with edges


    Abstract:

    An edge guard set of a plane graph $G$ is a subset $\Gamma$ of edges of $G$ such that each face of $G$ is incident to an endpoint of an edge in $\Gamma$. Such a set is said to guard $G$. We improve the known upper bounds on the number of edges required to guard any $n$-vertex embedded planar graph $G$:

    1. We present a simple inductive proof for a theorem of Everett and Rivera-Campo (1997) that $G$ can be guarded with at most $\frac{2n}{5}$ edges, then extend this approach with a deeper analysis to yield an improved bound of $\frac{3n}{8}$ edges for any plane graph.
    2. We prove that there exists an edge guard set of $G$ with at most $\frac{n}{3} + \frac{\alpha}{9}$ edges, where $\alpha$ is the number of quadrilateral faces in $G$. This improves the previous bound of $\frac{n}{3} + \alpha$ by Bose, Kirkpatrick, and Li (2003). Moreover, if there is no short path between any two quadrilateral faces in $G$, we show that $\frac{n}{3}$ edges suffice, removing the dependence on $\alpha$.
    With A. Biniaz, P. Bose, and A. Ooms.
    Graphs and Combinatorics, 35(2):437–450, 2019.
    pdf arXiv DOI Conference version SpringerLink 
    @article{edge-guarding-plane-graphs-journal,
  author={Biniaz, Ahmad and Bose, Prosenjit and Ooms, Aur\'elien and Verdonschot, Sander},
  title={Improved Bounds for Guarding Plane Graphs with Edges},
  journal={Graphs and Combinatorics},
  year={2019},
  volume={35},
  number={2},
  pages={437--450},
  doi={10.1007/s00373-018-02004-z}
}

  3. On plane constrained bounded-degree spanners


    Abstract: Let $P$ be a finite set of points in the plane and $S$ a set of non-crossing line segments with endpoints in $P$. The visibility graph of $P$ with respect to $S$, denoted $\textrm{Vis}(P,S)$, has vertex set $P$ and an edge for each pair of vertices $u,v$ in $P$ for which no line segment of $S$ properly intersects $uv$. We show that the constrained half-$\theta_6$-graph (which is identical to the constrained Delaunay graph whose empty visible region is an equilateral triangle) is a plane 2-spanner of $\textrm{Vis}(P,S)$. We then show how to construct a plane 6-spanner of $\textrm{Vis}(P,S)$ with maximum degree $6+c$, where $c$ is the maximum number of segments of $S$ incident to a vertex.
    With P. Bose, R. Fagerberg, and A. van Renssen.
    Algorithmica, 81(4):1392–1415, 2019.
    pdf arXiv DOI Conference version Algorithmica 
    @article{constrained-bounded-degree-spanners,
  author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander},
  title={On Plane Constrained Bounded-Degree Spanners},
  journal={Algorithmica},
  year={2019},
  volume={81},
  number={4},
  pages={1392--1415},
  doi={10.1007/s00453-018-0476-8}
}

  4. Dynamic graph coloring


    Abstract: In this paper we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a graph under insertion and deletion of vertices and edges. We present two algorithms that achieve different trade-offs between the number of recolorings and the number of colors used. For any $d>0$, the first algorithm maintains a proper $O(\mathcal{C} dN^{1/d})$-coloring while recoloring at most $O(d)$ vertices per update, where $\mathcal{C}$ and $N$ are the maximum chromatic number and maximum number of vertices, respectively. The second algorithm reverses the trade-off, maintaining an $O(\mathcal{C} d)$-coloring with $O(dN^{1/d})$ recolorings per update. The two converge when $d = \log N$, maintaining an $O(\mathcal{C} \log N)$-coloring with $O(\log N)$ recolorings per update. We also present a lower bound, showing that any algorithm that maintains a $c$-coloring of a $2$-colorable graph on $N$ vertices must recolor at least $\Omega(N^\frac2c(c-1))$ vertices per update, for any constant $c \geq 2$.
    With L. Barba, J. Cardinal, M. Korman, S. Langerman, A. van Renssen, and M. Roeloffzen.
    Algorithmica, 81(4):1319–1341, 2019.
    pdf arXiv DOI Conference version Algorithmica 
    @article{dynamic-graph-coloring-algo,
  author={Barba, Luis and Cardinal, Jean and Korman, Matias and Langerman, Stefan and van Renssen, Andr\'e and Roeloffzen, Marcel and Verdonschot, Sander},
  title={Dynamic Graph Coloring},
  journal={Algorithmica},
  year={2019},
  volume={81},
  number={4},
  pages={1319--1341},
  doi={10.1007/s00453-018-0473-y}
}

  5. Routing on the visibility graph


    Abstract: We consider the problem of routing on a network in the presence of line segment constraints (i.e., obstacles that edges in our network are not allowed to cross). Let $P$ be a set of $n$ points in the plane and let $S$ be a set of non-crossing line segments whose endpoints are in $P$. We present two deterministic 1-local $O(1)$-memory routing algorithms (i.e., the algorithms never look beyond the direct neighbours of the current location and store only a constant amount of additional information). These algorithms are guaranteed to find a path consisting of at most a linear number of edges between any pair of vertices of the visibility graph of $P$ subject to a set of constraints $S$. Contrary to all existing deterministic local routing algorithms, our routing algorithms do not route on a plane subgraph of the visibility graph. Additionally, we provide lower bounds on the routing ratio of any deterministic local routing algorithm on the visibility graph.
    With P. Bose, M. Korman, and A. van Renssen.
    Journal of Computational Geometry, 9(1):430–453, 2018.
    pdf arXiv DOI Conference version 
    @article{routing-visibility-graph-journal,
  author={Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Verdonschot, Sander},
  title={Routing on the Visibility Graph},
  journal={Journal of Computational Geometry},
  year={2018},
  volume={9},
  number={1},
  pages={430--453},
  doi={10.20382/jocg.v9i1a15}
}
  6. Flipping Edge-Labelled Triangulations

    Flipping edge-labelled triangulations


    Abstract:

    Flips in triangulations have received a lot of attention over the past decades. However, the problem of tracking where particular edges go during the flipping process has not been addressed. We examine this question by attaching unique labels to the triangulation edges. We also introduce the concept of the orbit of an edge $e$, which is the set of all edges reachable from $e$ via flips.

    We establish the first upper and lower bounds on the diameter of the flip graph in this setting. Specifically, we prove tight $\Theta(n \log n)$ bounds for edge-labelled triangulations of $n$-vertex convex polygons and combinatorial triangulations, contrasting with the $\Theta(n)$ bounds in their respective unlabelled settings. When simultaneous flips are allowed, the upper bound for convex polygons decreases to $O(\log^2 n)$, although we no longer have a matching lower bound.

    Moving beyond convex polygons, we show that edge-labelled triangulated polygons with a single reflex vertex can have a disconnected flip graph. This is in sharp contrast with the unlabelled case, where the flip graph is connected for any triangulated polygon. For spiral polygons, we provide a complete characterization of the orbits. This allows us to decide connectedness of the flip graph of a spiral polygon in linear time. We also prove an upper bound of $O(n^2)$ on the diameter of each connected component, which is optimal in the worst case. We conclude with an example of a non-spiral polygon whose flip graph has diameter $\Omega(n^3)$.

    With P. Bose, A. Lubiw, and V. Pathak.
    Computational Geometry: Theory and Applications, 68:309–326, 2018.
    Special Issue in Memory of Ferran Hurtado.
    pdf arXiv DOI 
    @article{edge-labelled-flips-CGTA,
  author={Bose, Prosenjit and Lubiw, Anna and Pathak, Vinayak and Verdonschot, Sander},
  title={Flipping Edge-Labelled Triangulations},
  journal={Computational Geometry: Theory and Applications},
  year={2018},
  volume={68},
  pages={309--326},
  note={Special Issue in Memory of Ferran Hurtado},
  doi={10.1016/j.comgeo.2017.06.005}
}
  7. Continuous {Y}ao Graphs

    Continuous Yao graphs


    Abstract:

    In this paper, we introduce a variation of the well-studied Yao graphs. Given a set of points $S\subset \mathbb{R}^2$ and an angle $0 < \theta \leq 2\pi$, we define the \emph{continuous Yao graph} $cY(\theta)$ with vertex set $S$ and angle $\theta$ as follows. For each $p,q\in S$, we add an edge from $p$ to $q$ in $cY(\theta)$ if there exists a cone with apex $p$ and aperture $\theta$ such that $q$ is a closest point to $p$ inside this cone.

    We study the spanning ratio of $cY(\theta)$ for different values of $\theta$. Using a new algebraic technique, we show that $cY(\theta)$ is a spanner when $\theta \leq 2\pi /3$. We believe that this technique may be of independent interest. We also show that $cY(\pi)$ is not a spanner, and that $cY(\theta)$ may be disconnected for $\theta > \pi$, but on the other hand is always connected for $\theta\leq \pi$. Furthermore, we show that $cY(\theta)$ is a region-fault-tolerant geometric spanner for convex fault regions when $\theta<\pi/3$. For half-plane faults, $cY(\theta)$ remains connected if $\theta\leq\pi$. Finally, we show that $cY(\theta)$ is not always self-approaching for any value of $\theta$.

    With D. Bakhshesh, L. Barba, P. Bose, J.-L. De Carufel, M. Damian, R. Fagerberg, M. Farshi, A. van Renssen, and P. Taslakian.
    Computational Geometry: Theory and Applications, 67:42–52, 2018.
    pdf DOI Conference version 
    @article{continuous-yao-graphs-cgta,
  author={Bakhshesh, Davood and Barba, Luis and Bose, Prosenjit and De Carufel, Jean-Lou and Damian, Mirela and Fagerberg, Rolf and Farshi, Mohammad and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander},
  title={Continuous {Y}ao Graphs},
  journal={Computational Geometry: Theory and Applications},
  year={2018},
  volume={67},
  pages={42--52},
  doi={10.1016/j.comgeo.2017.10.002}
}
  8. Competitive Local Routing with Constraints

    Competitive local routing with constraints


    Abstract: Let $P$ be a set of $n$ vertices in the plane and $S$ a set of non-crossing line segments between vertices in $P$, called constraints. Two vertices are visible if the straight line segment connecting them does not properly intersect any constraints. The constrained $\Theta_m$-graph is constructed by partitioning the plane around each vertex into $m$ disjoint cones, each with aperture $\theta = 2 \pi/m$, and adding an edge to the ‘closest’ visible vertex in each cone. We consider how to route on the constrained $\Theta_6$-graph. We first show that no deterministic 1-local routing algorithm is $o(\sqrt{n})$-competitive on all pairs of vertices of the constrained $\Theta_6$-graph. After that, we show how to route between any two visible vertices of the constrained $\Theta_6$-graph using only 1-local information. Our routing algorithm guarantees that the returned path is 2-competitive. Additionally, we provide a 1-local 18-competitive routing algorithm for visible vertices in the constrained half-$\Theta_6$-graph, a subgraph of the constrained $\Theta_6$-graph that is equivalent to the Delaunay graph where the empty region is an equilateral triangle. To the best of our knowledge, these are the first local routing algorithms in the constrained setting with guarantees on the length of the returned path.
    With P. Bose, R. Fagerberg, and A. van Renssen.
    Journal of Computational Geometry, 8(1):125–152, 2017.
    pdf arXiv DOI Conference version 
    @article{competitive-local-routing-with-constraints,
  author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander},
  title={Competitive Local Routing with Constraints},
  journal={Journal of Computational Geometry},
  year={2017},
  volume={8},
  number={1},
  pages={125--152},
  doi={10.20382/jocg.v8i1a7}
}

  9. Flips in edge-labelled pseudo-triangulations


    Abstract: Given a set of $n$ points in the plane, we show that $O(n^2)$ exchanging flips suffice to transform any edge-labelled pointed pseudo-triangulation into any other with the same set of labels. By using insertion, deletion and exchanging flips, we can transform any edge-labelled pseudo-triangulation into any other with $O(n \log c + h \log h)$ flips, where $c$ is the number of convex layers and $h$ is the number of points on the convex hull.
    With P. Bose.
    Computational Geometry: Theory and Applications, 60:45–54, 2017.
    Special issue for CCCG 2015.
    pdf arXiv DOI CGTA Conference version 
    @article{edge-labelled-pts,
  author={Bose, Prosenjit and Verdonschot, Sander},
  title={Flips in Edge-Labelled Pseudo-Triangulations},
  journal={Computational Geometry: Theory and Applications},
  year={2017},
  volume={60},
  pages={45--54},
  note={Special issue for CCCG 2015},
  doi={10.1016/j.comgeo.2016.08.001}
}

  10. Towards tight bounds on theta-graphs: More is not always better


    Abstract:

    We present improved upper and lower bounds on the spanning ratio of $\theta$-graphs with at least six cones. Given a set of points in the plane, a $\theta$-graph partitions the plane around each vertex into $m$ disjoint cones, each having aperture $\theta = 2 \pi/m$, and adds an edge to the ‘closest’ vertex in each cone. We show that for any integer $k \geq 1$, $\theta$-graphs with $4k + 2$ cones have a spanning ratio of $1 + 2 \sin(\theta/2)$ and we provide a matching lower bound, showing that this spanning ratio is tight.

    Next, we show that for any integer $k \geq 1$, $\theta$-graphs with $4k + 4$ cones have spanning ratio at most $1 + 2 \sin(\theta/2) / (\cos(\theta/2) - \sin(\theta/2))$. We also show that $\theta$-graphs with $4k + 3$ and $4k + 5$ cones have spanning ratio at most $\cos (\theta/4) / (\cos (\theta/2) - \sin (3\theta/4))$. This is a significant improvement on all families of $\theta$-graphs for which exact bounds are not known. For example, the spanning ratio of the $\theta$-graph with 7 cones is decreased from at most 7.5625 to at most 3.5132. These spanning proofs also imply improved upper bounds on the competitiveness of the $\theta$-routing algorithm. In particular, we show that the $\theta$-routing algorithm is $(1 + 2 \sin(\theta/2) / (\cos(\theta/2) - \sin(\theta/2)))$-competitive on $\theta$-graphs with $4k + 4$ cones and that this ratio is tight.

    Finally, we present improved lower bounds on the spanning ratio of these graphs. Using these bounds, we provide a partial order on these families of $\theta$-graphs. In particular, we show that $\theta$-graphs with $4k + 4$ cones have spanning ratio at least $1 + 2 \tan(\theta/2) + 2 \tan^2(\theta/2)$, where $\theta$ is $2 \pi / (4k + 4)$. This is somewhat surprising since, for equal values of $k$, the spanning ratio of $\theta$-graphs with $4k + 4$ cones is greater than that of $\theta$-graphs with $4k + 2$ cones, showing that increasing the number of cones can make the spanning ratio worse.

    With P. Bose, J.-L. De Carufel, P. Morin, and A. van Renssen.
    Theoretical Computer Science, 616:70–93, 2016.
    pdf arXiv DOI Conference version 1 Conference version 2 
    @article{bose2016towards,
  author={Bose, Prosenjit and De Carufel, Jean-Lou and Morin, Pat and van Renssen, Andr\'e and Verdonschot, Sander},
  title={Towards Tight Bounds on theta-Graphs: {M}ore is not always better},
  journal={Theoretical Computer Science},
  year={2016},
  volume={616},
  pages={70--93},
  doi={10.1016/j.tcs.2015.12.017}
}
  11. Optimal local routing on {D}elaunay triangulations defined by empty equilateral triangles

    Optimal local routing on Delaunay triangulations defined by empty equilateral triangles


    Abstract:

    We present a deterministic local routing algorithm that is guaranteed to find a path between any pair of vertices in a half-$\theta_6$-graph (the half-$\theta_6$-graph is equivalent to the Delaunay triangulation where the empty region is an equilateral triangle). The length of the path is at most $5/\sqrt{3} \approx 2.887$ times the Euclidean distance between the pair of vertices. Moreover, we show that no local routing algorithm can achieve a better routing ratio, thereby proving that our routing algorithm is optimal. This is somewhat surprising because the spanning ratio of the half-$\theta_6$-graph is 2, meaning that even though there always exists a path whose lengths is at most twice the Euclidean distance, we cannot always find such a path when routing locally.

    Since every triangulation can be embedded in the plane as a half-$\theta_6$-graph using $O(\log n)$ bits per vertex coordinate via Schnyder’s embedding scheme (SODA 1990), our result provides a competitive local routing algorithm for every such embedded triangulation. Finally, we show how our routing algorithm can be adapted to provide a routing ratio of $15/\sqrt{3} \approx 8.660$ on two bounded degree subgraphs of the half-$\theta_6$-graph.

    With P. Bose, R. Fagerberg, and A. van Renssen.
    SIAM Journal on Computing, 44(6):1626–1649, 2015.
    pdf arXiv DOI Conference version 1 Conference version 2 
    @article{bose2015optimal,
  author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander},
  title={Optimal local routing on {D}elaunay triangulations defined by empty equilateral triangles},
  journal={SIAM Journal on Computing},
  year={2015},
  volume={44},
  number={6},
  pages={1626--1649},
  doi={10.1137/140988103}
}
  12. New and Improved Spanning Ratios for {Y}ao Graphs

    New and improved spanning ratios for Yao graphs


    Abstract:

    For a set of points in the plane and a fixed integer $k > 0$, the Yao graph $Y_k$ partitions the space around each point into $k$ equiangular cones of angle $\theta=2\pi/k$, and connects each point to a nearest neighbor in each cone. It is known for all Yao graphs, with the sole exception of $Y_5$, whether or not they are geometric spanners. In this paper we close this gap by showing that for odd $k \geq 5$, the spanning ratio of $Y_k$ is at most $1/(1-2\sin(3\theta/8))$, which gives the first constant upper bound for $Y_5$, and is an improvement over the previous bound of $1/(1-2\sin(\theta/2))$ for odd $k \geq 7$.

    We further reduce the upper bound on the spanning ratio for $Y_5$ from $10.9$ to $2+\sqrt{3} \approx 3.74$, which falls slightly below the lower bound of $3.79$ established for the spanning ratio of $\Theta_5$ ($\Theta$-graphs differ from Yao graphs only in the way they select the closest neighbor in each cone). This is the first such separation between a Yao and $\Theta$-graph with the same number of cones. We also give a lower bound of $2.87$ on the spanning ratio of $Y_5$.

    In addition, we revisit the $Y_6$ graph, which plays a particularly important role as the transition between the graphs ($k > 6$) for which simple inductive proofs are known, and the graphs ($k \le 6$) whose best spanning ratios have been established by complex arguments. Here we reduce the known spanning ratio of $Y_6$ from $17.6$ to $5.8$, getting closer to the spanning ratio of 2 established for $\Theta_6$.

    Finally, we present the first lower bounds on the spanning ratio of Yao graphs with more than six cones, and a construction that shows that the Yao-Yao graph (a bounded-degree variant of the Yao graph) with five cones is not a spanner.

    With L. Barba, P. Bose, M. Damian, R. Fagerberg, W. L. Keng, J. O’Rourke, A. van Renssen, P. Taslakian, and G. Xia.
    Journal of Computational Geometry, 6(2):19–53, 2015.
    Special issue for SoCG 2014.
    pdf arXiv DOI JoCG Conference version 
    @article{barba2014newJournal,
  author={Barba, Luis and Bose, Prosenjit and Damian, Mirela and Fagerberg, Rolf and Keng, Wah Loon and O'Rourke, Joseph and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander and Xia, Ge},
  title={New and Improved Spanning Ratios for {Y}ao Graphs},
  journal={Journal of Computational Geometry},
  year={2015},
  volume={6},
  number={2},
  pages={19--53},
  note={Special issue for SoCG 2014},
  doi={10.20382/jocg.v6i2a3}
}
  13. The {$\theta_5$}-graph is a spanner

    The $\theta_5$-graph is a spanner


    Abstract: Given a set of points in the plane, we show that the $\theta$-graph with 5 cones is a geometric spanner with spanning ratio at most $\sqrt{50 + 22 \sqrt{5}} \approx 9.960$. This is the first constant upper bound on the spanning ratio of this graph. The upper bound uses a constructive argument that gives a (possibly self-intersecting) path between any two vertices, of length at most $\sqrt{50 + 22 \sqrt{5}}$ times the Euclidean distance between the vertices. We also give a lower bound on the spanning ratio of $\frac{1}{2}(11\sqrt{5} -17) \approx 3.798$.
    With P. Bose, P. Morin, and A. van Renssen.
    Computational Geometry: Theory and Applications, 48(2):108–119, 2015.
    pdf arXiv DOI Conference version 
    @article{bose2013theta5journal,
  author={Bose, Prosenjit and Morin, Pat and van Renssen, Andr\'e and Verdonschot, Sander},
  title={The {$\theta_5$}-graph is a spanner},
  journal={Computational Geometry: Theory and Applications},
  year={2015},
  volume={48},
  number={2},
  pages={108--119},
  doi={10.1016/j.comgeo.2014.08.005}
}

  14. On the number of regular edge labelings


    Abstract: We prove that any irreducible triangulation on $n$ vertices has $O(4.6807^n)$ regular edge labelings and that there are irreducible triangulations on $n$ vertices with $\Omega(3.0426^n)$ regular edge labelings.
    With K. Buchin and B. Speckmann.
    Discrete Mathematics & Theoretical Computer Science, 16(3):215–228, 2014.
    pdf DMTCS Conference version 
    @article{buchin2014number,
  author={Buchin, Kevin and Speckmann, Bettina and Verdonschot, Sander},
  title={On the Number of Regular Edge Labelings},
  journal={Discrete Mathematics {\&} Theoretical Computer Science},
  year={2014},
  volume={16},
  number={3},
  pages={215--228}
}
  15. Theta-3 is connected

    Theta-3 is connected


    Abstract: In this paper, we show that the $\theta$-graph with three cones is connected. We also provide an alternative proof of the connectivity of the Yao-graph with three cones.
    With O. Aichholzer, S. W. Bae, L. Barba, P. Bose, M. Korman, A. van Renssen, and P. Taslakian.
    Computational Geometry: Theory and Applications, 47(9):910–917, 2014.
    Special issue for CCCG 2013.
    pdf arXiv DOI Conference version 
    @article{aichholzer2013theta3journal,
  author={Aichholzer, Oswin and Bae, Sang Won and Barba, Luis and Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander},
  title={Theta-3 is connected},
  journal={Computational Geometry: Theory and Applications},
  year={2014},
  volume={47},
  number={9},
  pages={910--917},
  note={Special issue for CCCG 2013},
  doi={10.1016/j.comgeo.2014.05.001}
}
  16. Making triangulations 4-connected using flips

    Making triangulations 4-connected using flips


    Abstract: We show that any combinatorial triangulation on $n$ vertices can be transformed into a 4-connected one using at most $\lfloor(3n - 9)/5\rfloor$ edge flips. We also give an example of an infinite family of triangulations that requires this many flips to be made 4-connected, showing that our bound is tight. In addition, for $n \geq 19$, we improve the upper bound on the number of flips required to transform any 4-connected triangulation into the canonical triangulation (the triangulation with two dominant vertices), matching the known lower bound of $2n - 15$. Our results imply a new upper bound on the diameter of the flip graph of $5.2 n - 33.6$, improving on the previous best known bound of $6n - 30$.
    With P. Bose, D. Jansens, A. van Renssen, and M. Saumell.
    Computational Geometry: Theory and Applications, 47(2A):187–197, 2014.
    Special issue for CCCG 2011.
    pdf arXiv DOI Conference version 
    @article{bose2014making,
  author={Bose, Prosenjit and Jansens, Dana and van Renssen, Andr\'e and Saumell, Maria and Verdonschot, Sander},
  title={Making triangulations 4-connected using flips},
  journal={Computational Geometry: Theory and Applications},
  year={2014},
  volume={47},
  number={2A},
  pages={187--197},
  note={Special issue for CCCG 2011},
  doi={10.1016/j.comgeo.2012.10.012}
}

Submitted Journal Conference Chapters Theses Talks

Conference papers

Conference papers that I presented are marked with (presented).
(Icon by Double-J Design, used under a Creative Commons Attribution license)

  1. On convex polygons in cartesian products


    Abstract: We study several problems concerning convex polygons whose vertices lie in a Cartesian product of two sets of $n$ real numbers (for short, grid). First, we prove that every such grid contains a convex polygon with $\Omega(\log n)$ vertices and that this bound is tight up to a constant factor. We generalize this result to $d$ dimensions (for a fixed $d\in \mathbb{N}$), and obtain a tight lower bound of $\Omega(\log^d-1n)$ for the maximum number of points in convex position in a $d$-dimensional grid. Second, we present polynomial-time algorithms for computing the longest convex polygonal chain in a grid that contains no two points with the same $x$- or $y$-coordinate. We show that the maximum size of such a convex polygon can be efficiently approximated up to a factor of $2$. Finally, we present exponential bounds on the maximum number of convex polygons in these grids, and for some restricted variants. These bounds are tight up to polynomial factors.
    With J.-L. De Carufel, A. Dumitrescu, W. Meulemans, T. Ophelders, C. Pennarun, and C. D. Tóth.
    Accepted to the 35th Annual Symposium on Computational Geometry (SoCG 2019).
    pdf arXiv EuroCG 
    @inproceedings{convex-polygons-cartesian-products-conf,
  author={De Carufel, Jean-Lou and Dumitrescu, Adrian and Meulemans, Wouter and Ophelders, Tim and Pennarun, Claire and T\'oth, Csaba D. and Verdonschot, Sander},
  title={On Convex Polygons in Cartesian Products},
  booktitle={Proceedings of the 35th Annual Symposium on Computational Geometry (SoCG 2019)},
  year={2018}
}

  2. Reconstructing a convex polygon from its $\omega$-cloud


    Abstract:

    An $\omega$-wedge consists of two rays emanating from a single point (the apex), separated by an angle $\omega < \pi$. Given a convex polygon $P$, we place the $\omega$-wedge such that $P$ is inside the wedge and both rays are tangent to $P$. The $\omega$-cloud of $P$ is the curve traced by the apex of the $\omega$-wedge as it rotates around $P$ while maintaining tangency in both rays.

    Previous work crucially required knowledge of the points of tangency of the $\omega$-wedge to reconstruct $P$. We show that if $\omega$ is known, the $\omega$-cloud alone uniquely determines $P$, and we give a linear-time reconstruction algorithm. Furthermore, even if we only know that $\omega < \pi/2$, we can still reconstruct $P$, albeit in cubic time in the number of vertices. This reduces to quadratic time if in addition we are given the location of one of the vertices of $P$.

    With P. Bose, J.-L. De Carufel, and E. Khramtcova.
    Accepted to the 14th International Computer Science Symposium in Russia (CSR 2019).
    pdf arXiv EuroCG 
    @inproceedings{reconstructing-omega-cloud-conf,
  author={Bose, Prosenjit and De Carufel, Jean-Lou and Khramtcova, Elena and Verdonschot, Sander},
  title={Reconstructing a convex polygon from its $\omega$-cloud},
  booktitle={Proceedings of the 14th International Computer Science Symposium in Russia (CSR 2019)},
  year={2019}
}

  3. Improved bounds for guarding plane graphs with edges


    Abstract:

    An edge guard set of a plane graph $G$ is a subset $\Gamma$ of edges of $G$ such that each face of $G$ is incident on an endpoint of an edge in $\Gamma$. Such a set is said to guard $G$. We improve the known upper bounds on the number of edges required to guard any $n$-vertex embedded planar graph $G$:

    1. We present a simple inductive proof for a theorem of Everett and Rivera-Campo (1997) that $G$ can be guarded with at most $\frac{2n}{5}$ edges, then extend the same approach to yield an improved bound of $\frac{3n}{8}$ edges for any plane graph.
    2. We prove that there exists an edge guard set of $G$ with at most $\frac{n}{3} + \frac{\alpha}{9}$ edges, where $\alpha$ is the number of quadrilateral faces in $G$. This improves the previous bound of $\frac{n}{3} + \alpha$ by Bose, Kirkpatrick, and Li (2003). Moreover, if there is no short path between any two quadrilateral faces in $G$, we show that $\frac{n}{3}$ edges suffice, removing the dependence on $\alpha$.
    With A. Biniaz, P. Bose, and A. Ooms.
    In Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), pages 14:1–14:12, 2018.
    arXiv DOI Journal version SWAT 
    @inproceedings{edge-guarding-plane-graphs-conf,
  author={Biniaz, Ahmad and Bose, Prosenjit and Ooms, Aur\'elien and Verdonschot, Sander},
  title={Improved Bounds for Guarding Plane Graphs with Edges},
  booktitle={Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  year={2018},
  volume={101},
  series={Leibniz International Proceedings in Informatics (LIPIcs)},
  pages={14:1--14:12},
  doi={10.4230/LIPIcs.SWAT.2018.14}
}

  4. Routing on the visibility graph


    Abstract: We consider the problem of routing on a network in the presence of line segment constraints (i.e., obstacles that edges in our network are not allowed to cross). Let $P$ be a set of $n$ points in the plane and let $S$ be a set of non-crossing line segments whose endpoints are in $P$. We present two deterministic 1-local $O(1)$-memory routing algorithms that are guaranteed to find a path of at most linear size between any pair of vertices of the visibility graph of $P$ with respect to a set of constraints $S$ (i.e., the algorithms never look beyond the direct neighbours of the current location and store only a constant amount of information). Contrary to all existing deterministic local routing algorithms, our routing algorithms do not route on a plane subgraph of the visibility graph.
    With P. Bose, M. Korman, and A. van Renssen.
    In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017), pages 18:1–18:12, 2017.
    pdf arXiv DOI URL Journal version 
    @inproceedings{routing-visibility-graph-isaac,
  author={Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Verdonschot, Sander},
  title={Routing on the Visibility Graph},
  booktitle={Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  year={2017},
  volume={92},
  series={Leibniz International Proceedings in Informatics (LIPIcs)},
  pages={18:1--18:12},
  doi={10.4230/LIPIcs.ISAAC.2017.18},
  url={http://drops.dagstuhl.de/opus/volltexte/2017/8222}
}

  5. Constrained routing between non-visible vertices


    Abstract: Routing is an important problem in networks. We look at routing in the presence of line segment constraints (i.e., obstacles that our edges are not allowed to cross). Let $P$ be a set of $n$ vertices in the plane and let $S$ be a set of line segments between the vertices in $P$, with no two line segments intersecting properly. We present the first 1-local $O(1)$-memory routing algorithm on the visibility graph of $P$ with respect to a set of constraints $S$ (i.e., it never looks beyond the direct neighbours of the current location and does not need to store more than $O(1)$-information to reach the target). We also show that when routing on any triangulation $T$ of $P$ such that $S\subseteq T$, no $o(n)$-competitive routing algorithm exists when only considering the triangles intersected by the line segment from the source to the target (a technique commonly used in the unconstrained setting). Finally, we provide an $O(n)$-competitive 1-local $O(1)$-memory routing algorithm on any such $T$, which is optimal in the worst case, given the lower bound.
    With P. Bose, M. Korman, and A. van Renssen.
    In Proceedings of the 23rd Annual International Computing and Combinatorics Conference (COCOON 2017), pages 62–74, 2017.
    pdf arXiv DOI Journal version 
    @inproceedings{non-visible-constrained-routing-cocoon,
  author={Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Verdonschot, Sander},
  title={Constrained Routing Between Non-Visible Vertices},
  booktitle={Proceedings of the 23rd Annual International Computing and Combinatorics Conference (COCOON 2017)},
  year={2017},
  pages={62--74},
  doi={10.1007/978-3-319-62389-4_6}
}

  6. Dynamic graph coloring

    (presented)
    Abstract: In this paper we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a graph under insertion and deletion of vertices and edges. We present two algorithms that achieve different trade-offs between the number of recolorings and the number of colors used. For any $d>0$, the first algorithm maintains a proper $O(\mathcal{C} dN^{1/d})$-coloring while recoloring at most $O(d)$ vertices per update, where $\mathcal{C}$ and $N$ are the maximum chromatic number and maximum number of vertices, respectively. The second algorithm reverses the trade-off, maintaining an $O(\mathcal{C} d)$-coloring with $O(dN^{1/d})$ recolorings per update. We also present a lower bound, showing that any algorithm that maintains a $c$-coloring of a $2$-colorable graph on $N$ vertices must recolor at least $\Omega(N^\frac2c(c-1))$ vertices per update, for any constant $c \geq 2$.
    With L. Barba, J. Cardinal, M. Korman, S. Langerman, A. van Renssen, and M. Roeloffzen.
    In Proceedings of the 15th Algorithms and Data Structures Symposium (WADS 2017), pages 97–108, 2017.
    pdf arXiv DOI Journal version Slides (pdf) 
    @inproceedings{dynamic-graph-coloring-wads,
  author={Barba, Luis and Cardinal, Jean and Korman, Matias and Langerman, Stefan and van Renssen, Andr\'e and Roeloffzen, Marcel and Verdonschot, Sander},
  title={Dynamic Graph Coloring},
  booktitle={Proceedings of the 15th Algorithms and Data Structures Symposium (WADS 2017)},
  year={2017},
  pages={97--108},
  doi={10.1007/978-3-319-62127-2_9}
}

  7. Power domination on triangular grids


    Abstract: The concept of power domination emerged from the problem of monitoring electrical systems. Given a graph $G$ and a set $S \subseteq V(G)$, a vertex $v$ is said to be monitored if either $v$ is a neighbor of $S$, or there is a vertex $u \in N(v)$ such that $v$ is the only non-monitored vertex of $u$. The power domination number of a graph $G$ is the minimum size of a set $S$ such that this process monitors every vertex of the graph. We here show that the power domination number of a triangular grid $T_k$ with hexagonal-shape border of length $k − 1$ is exactly $\lceil k / 3 \rceil$
    With P. Bose and C. Pennarun.
    In Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017), pages 2–6, 2017.
    pdf arXiv Talk 
    @inproceedings{power-domination-triangular-grids-cccg,
  author={Bose, Prosenjit and Pennarun, Claire and Verdonschot, Sander},
  title={Power domination on triangular grids},
  booktitle={Proceedings of the 29th Canadian Conference on Computational Geometry (CCCG 2017)},
  year={2017},
  pages={2--6}
}

  8. Gabriel triangulations and angle-monotone graphs: local routing and recognition


    Abstract: A geometric graph is angle-monotone if every pair of vertices has a path between them that—after some rotation—is $x$- and $y$-monotone. Angle-monotone graphs are $\sqrt 2$-spanners and they are increasing-chord graphs. Dehkordi, Frati, and Gudmundsson introduced angle-monotone graphs in 2014 and proved that Gabriel triangulations are angle-monotone graphs. We give a polynomial time algorithm to recognize angle-monotone geometric graphs. We prove that every point set has a plane geometric graph that is generalized angle-monotone—specifically, we prove that the half-$\Theta_6$-graph is generalized angle-monotone. We give a local routing algorithm for Gabriel triangulations that finds a path from any vertex $s$ to any vertex $t$ whose length is within $1 + \sqrt 2$ times the Euclidean distance from $s$ to $t$. Finally, we prove some lower bounds and limits on local routing algorithms on Gabriel triangulations.
    With N. Bonichon, P. Bose, P. Carmi, I. Kostitsyna, and A. Lubiw.
    In Proceedings of the 24th International Symposium on Graph drawing (GD 2016), pages 519–531, 2016.
    pdf arXiv 
    @inproceedings{angle-monotone-graphs,
  author={Bonichon, Nicolas and Bose, Prosenjit and Carmi, Paz and Kostitsyna, Irina and Lubiw, Anna and Verdonschot, Sander},
  title={Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition},
  booktitle={Proceedings of the 24th International Symposium on Graph drawing (GD 2016)},
  year={2016},
  pages={519--531}
}

  9. Realizing farthest-point Voronoi diagrams


    Abstract: The farthest-point Voronoi diagram of a set of $n$ sites is a tree with $n$ leaves. We investigate whether arbitrary trees can be realized as farthest-point Voronoi diagrams. Given an abstract ordered tree $T$ with $n$ leaves and prescribed edge lengths, we produce a set of $n$ sites $S$ in $O(n)$ time such that the farthest-point Voronoi diagram of $S$ represents $T$. We generalize this algorithm to smooth strictly convex symmetric distance functions. Furthermore, when given a subdivision $Z$ of $\mathbb{R}^k$, we check in linear time whether $Z$ realizes a $k$-dimensional farthest-point Voronoi diagram when $k$ is a constant.
    With T. Biedl, C. Grimm, L. Palios, and J. Shewchuk.
    In Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016), pages 48–56, 2016.
    pdf 
    @inproceedings{realizing-farthest-point-VD,
  author={Biedl, Therese and Grimm, Carsten and Palios, Leonidas and Shewchuk, Jonathan and Verdonschot, Sander},
  title={Realizing Farthest-Point {V}oronoi Diagrams},
  booktitle={Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016)},
  year={2016},
  pages={48--56}
}

  10. Rectangle-of-influence triangulations

    (presented)
    Abstract: A rectangle-of-influence (RI) drawing is a straight-line drawing where for every edge $(u,v)$ the minimum axis-aligned rectangle containing $u$ and $v$ contains no other points. In this paper, we show how to create RI-triangulations (i.e., triangulations that are RI-drawings) for any point set. Moreover, by using the $L^\infty$-Delaunay-triangulations, we show that we can flip from any RI-triangulation to any other while maintaining RI-triangulations.
    With T. Biedl, A. Lubiw, and S. Mehrabi.
    In Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016), pages 237–243, 2016.
    pdf Slides (pdf) 
    @inproceedings{rectangle-of-influence-triangulations,
  author={Biedl, Therese and Lubiw, Anna and Mehrabi, Saeed and Verdonschot, Sander},
  title={Rectangle-of-influence triangulations},
  booktitle={Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016)},
  year={2016},
  pages={237--243}
}

  11. Competitive local routing with constraints


    Abstract:

    Let $P$ be a set of $n$ points in the plane and $S$ a set of non-crossing line segments between vertices in $P$, called constraints. Two vertices are visible if the straight line segment connecting them does not properly intersect any constraints. The constrained $\theta_m$-graph is constructed by partitioning the plane around each vertex into $m$ disjoint cones, each with aperture $\theta = 2 \pi/m$, and adding an edge to the ‘closest’ visible vertex in each cone. We consider how to route on the constrained $\theta_6$-graph.

    We first show that no deterministic 1-local routing algorithm is $o(\sqrt{n})$-competitive on all pairs of vertices of the constrained $\theta_6$-graph. After that, we show how to route between any two visible vertices of the constrained $\theta_6$-graph using only 1-local information. Our routing algorithm guarantees that the returned path has length at most 2 times the Euclidean distance between the source and destination. Additionally, we provide a 1-local 18-competitive routing algorithm for visible vertices in the constrained \graph, a subgraph of the constrained $\theta_6$-graph that is equivalent to the Delaunay graph where the empty region is an equilateral triangle. To the best of our knowledge, these are the first local routing algorithms in the constrained setting with guarantees on the length of the returned path.

    With P. Bose, R. Fagerberg, and A. van Renssen.
    In Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC 2015), pages 23–34, 2015.
    pdf arXiv DOI Journal version 
    @inproceedings{bose2015competitive,
  author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander},
  title={Competitive local routing with constraints},
  booktitle={Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC 2015)},
  year={2015},
  pages={23--34},
  doi={10.1007/978-3-662-48971-0_3}
}

  12. Flips in edge-labelled pseudo-triangulations

    (presented)
    Abstract: We show that $O(n^2)$ exchanging flips suffice to transform any edge-labelled pointed pseudo-triangulation into any other with the same set of labels. By using insertion, deletion and exchanging flips, we can transform any edge-labelled pseudo-triangulation into any other with $O(n \log c + h \log h)$ flips, where $c$ is the number of convex layers and $h$ is the number of points on the convex hull.
    With P. Bose.
    In Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG 2015), pages 63–69, 2015.
    pdf Slides (pdf) Journal version 
    @inproceedings{bose2015flips,
  author={Bose, Prosenjit and Verdonschot, Sander},
  title={Flips in Edge-Labelled Pseudo-Triangulations},
  booktitle={Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG 2015)},
  year={2015},
  pages={63--69}
}

  13. Continuous Yao graphs


    Abstract:

    In this paper, we introduce a variation of the well-studied Yao graphs. Given a set of points $S\subset \mathbb{R}^2$ and an angle $0 < \theta \leq 2\pi$, we define the continuous Yao graph $cY(\theta)$ with vertex set $S$ and angle $\theta$ as follows. For each $p,q\in S$, we add an edge from $p$ to $q$ in $cY(\theta)$ if there exists a cone with apex $p$ and aperture $\theta$ such that $q$ is the closest point to $p$ inside this cone.

    We study the spanning ratio of $cY(\theta)$ for different values of $\theta$. Using a new algebraic technique, we show that $cY(\theta)$ is a spanner when $\theta \leq 2\pi /3$. We believe that this technique may be of independent interest. We also show that $cY(\pi)$ is not a spanner, and that $cY(\theta)$ may be disconnected for $\theta > \pi$.

    With L. Barba, P. Bose, J.-L. De Carufel, M. Damian, R. Fagerberg, A. van Renssen, and P. Taslakian.
    In Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG 2014), pages 100–106, 2014.
    pdf arXiv Journal version 
    @inproceedings{barba2014continuous,
  author={Barba, Luis and Bose, Prosenjit and De Carufel, Jean-Lou and Damian, Mirela and Fagerberg, Rolf and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander},
  title={Continuous {Y}ao Graphs},
  booktitle={Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG 2014)},
  year={2014},
  pages={100--106}
}

  14. Weight balancing on boundaries and skeletons


    Abstract: Given a polygonal region containing a target point (which we assume is the origin), it is not hard to see that there are two points on the perimeter that are antipodal, i.e., whose midpoint is the origin. We prove three generalizations of this fact.
    1. For any polygon (or any bounded closed region with connected boundary) containing the origin, it is possible to place a given set of weights on the boundary so that their barycenter (center of mass) coincides with the origin, provided that the largest weight does not exceed the sum of the other weights.
    2. On the boundary of any 3-dimensional bounded polyhedron containing the origin, there exist three points that form an equilateral triangle centered at the origin.
    3. On the 1-skeleton of any 3-dimensional bounded convex polyhedron containing the origin, there exist three points whose center of mass coincides with the origin.
    With L. Barba, O. Cheong, J.-L. De Carufel, M. Dobbins, R. Fleischer, A. Kawamura, M. Korman, Y. Okamoto, J. Pach, Y. Tang, T. Tokuyama, and T. Wang.
    In Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG 2014), pages 436–443, 2014.
    pdf DOI 
    @inproceedings{barba2014weight,
  author={Barba, Luis and Cheong, Otfried and De Carufel, Jean-Lou and Dobbins, Michael and Fleischer, Rudolf and Kawamura, Akitoshi and Korman, Matias and Okamoto, Yoshio and Pach, J\'anos and Tang, Yuan and Tokuyama, Takeshi and Verdonschot, Sander and Wang, Tianhao},
  title={Weight Balancing on Boundaries and Skeletons},
  booktitle={Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG 2014)},
  year={2014},
  pages={436--443},
  doi={10.1145/2582112.2582142}
}

  15. New and improved spanning ratios for Yao graphs

    (presented)
    Abstract:

    For a set of points in the plane and a fixed integer $k > 0$, the Yao graph $Y_k$ partitions the space around each point into $k$ equiangular cones of angle $\theta=2\pi/k$, and connects each point to a nearest neighbor in each cone. It is known for all Yao graphs, with the sole exception of $Y_5$, whether or not they are geometric spanners. In this paper we close this gap by showing that for odd $k \geq 5$, the spanning ratio of $Y_k$ is at most $1/(1-2\sin(3\theta/8))$, which gives the first constant upper bound for $Y_5$, and is an improvement over the previous bound of $1/(1-2\sin(\theta/2))$ for odd $k \geq 7$.

    We further reduce the upper bound on the spanning ratio for $Y_5$ from $10.9$ to $2+\sqrt{3} \approx 3.74$, which falls slightly below the lower bound of $3.79$ established for the spanning ratio of $\Theta_5$ ($\Theta$-graphs differ from Yao graphs only in the way they select the closest neighbor in each cone). This is the first such separation between a Yao and $\Theta$-graph with the same number of cones. We also give a lower bound of $2.87$ on the spanning ratio of $Y_5$.

    Finally, we revisit the $Y_6$ graph, which plays a particularly important role as the transition between the graphs ($k > 6$) for which simple inductive proofs are known, and the graphs ($k \le 6$) whose best spanning ratios have been established by complex arguments. Here we reduce the known spanning ratio of $Y_6$ from $17.6$ to $5.8$, getting closer to the spanning ratio of 2 established for $\Theta_6$.

    With L. Barba, P. Bose, M. Damian, R. Fagerberg, W. L. Keng, J. O’Rourke, A. van Renssen, P. Taslakian, and G. Xia.
    In Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG 2014), pages 30–39, 2014.
    pdf arXiv DOI Slides (pdf) Journal version 
    @inproceedings{barba2014new,
  author={Barba, Luis and Bose, Prosenjit and Damian, Mirela and Fagerberg, Rolf and Keng, Wah Loon and O'Rourke, Joseph and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander and Xia, Ge},
  title={New and Improved Spanning Ratios for {Y}ao Graphs},
  booktitle={Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG 2014)},
  year={2014},
  pages={30--39},
  doi={10.1145/2582112.2582143}
}

  16. On the average number of edges in Theta graphs


    Abstract: Theta graphs are important geometric graphs that have many applications, including wireless networking, motion planning, real-time animation, and minimum-spanning tree construction. We give closed form expressions for the average degree of theta graphs of a homogeneous Poisson point process over the plane. We then show that essentially the same bounds—with vanishing error terms—hold for theta graphs of finite sets of points that are uniformly distributed in a square. Finally, we show that the number of edges in a theta graph of points uniformly distributed in a square is concentrated around its expected value.
    With P. Morin.
    In Proceedings of the 11th Meeting on Analytic Algorithmics and Combinatorics (ANALCO14), pages 121–132, 2014.
    pdf arXiv DOI Journal version Mathematica code 
    @inproceedings{morin2013average,
  author={Morin, Pat and Verdonschot, Sander},
  title={On the Average Number of Edges in {T}heta Graphs},
  booktitle={Proceedings of the 11th Meeting on Analytic Algorithmics and Combinatorics (ANALCO14)},
  year={2014},
  pages={121--132},
  doi={10.1137/1.9781611973204.12}
}

  17. On the spanning ratio of Theta-graphs


    Abstract: We present improved upper bounds on the spanning ratio of a large family of $\theta$-graphs. A $\theta$-graph partitions the plane around each vertex into $m$ disjoint cones, each having aperture $\theta = 2 \pi/m$. We show that for any integer $k \geq 1$, $\theta$-graphs with $4k + 4$ cones have spanning ratio at most $1 + 2 \sin(\theta/2) / (\cos(\theta/2) - \sin(\theta/2))$. We also show that $\theta$-graphs with $4k + 3$ and $4k + 5$ cones have spanning ratio at most $\cos (\theta/4) / (\cos (\theta/2) - \sin (3\theta/4))$. This is a significant improvement on all families of $\theta$-graphs for which exact bounds are not known. For example, the spanning ratio of the $\theta$-graph with 7 cones is decreased from at most 7.5625 to at most 3.5132. We also improve the upper bounds on the competitiveness of the $\theta$-routing algorithm for these graphs to $1 + 2 \sin(\theta/2) / (\cos(\theta/2) - \sin(\theta/2))$ on $\theta$-graphs with $4k + 4$ cones and to $1 + 2 \sin(\theta/2) \cdot \cos (\theta/4) / (\cos (\theta/2) - \sin (3\theta/4))$ on $\theta$-graphs with $4k + 3$ and $4k + 5$ cones. For example, the routing ratio of the $\theta$-graph with 7 cones is decreased from at most 7.5625 to at most 4.0490.
    With P. Bose and A. van Renssen.
    In Proceedings of the 13th Algorithms and Data Structures Symposium (WADS 2013), pages 182–194, 2013.
    pdf DOI Journal version 
    @inproceedings{bose2013spanning,
  author={Bose, Prosenjit and van Renssen, Andr\'e and Verdonschot, Sander},
  title={On the Spanning Ratio of {T}heta-Graphs},
  booktitle={Proceedings of the 13th Algorithms and Data Structures Symposium (WADS 2013)},
  year={2013},
  pages={182--194},
  doi={10.1007/978-3-642-40104-6_16}
}

  18. On the stretch factor of the Theta-4 graph


    Abstract: In this paper we show that the $\theta$-graph with 4 cones has constant stretch factor, i.e., there is a path between any pair of vertices in this graph whose length is at most a constant times the Euclidean distance between that pair of vertices. This is the last $\theta$-graph for which it was not known whether its stretch factor was bounded.
    With L. Barba, P. Bose, J.-L. De Carufel, and A. van Renssen.
    In Proceedings of the 13th Algorithms and Data Structures Symposium (WADS 2013), pages 109–120, 2013.
    pdf arXiv DOI 
    @inproceedings{barba2013stretch,
  author={Barba, Luis and Bose, Prosenjit and De Carufel, Jean-Lou and van Renssen, Andr\'e and Verdonschot, Sander},
  title={On the stretch factor of the {T}heta-4 graph},
  booktitle={Proceedings of the 13th Algorithms and Data Structures Symposium (WADS 2013)},
  year={2013},
  pages={109--120},
  doi={10.1007/978-3-642-40104-6_10}
}

  19. Theta-3 is connected

    (presented)
    Abstract: In this paper, we show that the $\theta$-graph with three cones is connected. We also provide an alternative proof of the connectivity of the Yao-graph with three cones.
    With O. Aichholzer, S. W. Bae, L. Barba, P. Bose, M. Korman, A. van Renssen, and P. Taslakian.
    In Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), pages 205–210, 2013.
    pdf arXiv Slides (pdf) Journal version 
    @inproceedings{aichholzer2013theta3,
  author={Aichholzer, Oswin and Bae, Sang Won and Barba, Luis and Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'e and Taslakian, Perouz and Verdonschot, Sander},
  title={Theta-3 is connected},
  booktitle={Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013)},
  year={2013},
  pages={205--210}
}

  20. The $\theta_5$-graph is a spanner

    (presented)
    Abstract: We show that the $\theta$-graph with 5 cones is a geometric spanner with spanning ratio at most $\sqrt{50 + 22 \sqrt{5}} \approx 9.960$. This is the first constant upper bound on the spanning ratio of this graph. The upper bound uses a constructive argument, giving a, possibly non-planar, spanning path between any two vertices. We also give a lower bound on the spanning ratio of $\frac{1}{2}(11\sqrt{5} -17) \approx 3.798$.
    With P. Bose, P. Morin, and A. van Renssen.
    In Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013), pages 100–114, 2013.
    pdf arXiv DOI Slides (pdf) Journal version 
    @inproceedings{bose2013theta5,
  author={Bose, Prosenjit and Morin, Pat and van Renssen, Andr\'e and Verdonschot, Sander},
  title={The {$\theta_5$}-graph is a spanner},
  booktitle={Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013)},
  year={2013},
  pages={100--114},
  doi={10.1007/978-3-642-45043-3_10}
}

  21. Competitive routing on a bounded-degree plane spanner

    (presented)
    Abstract: We show that it is possible to route locally and competitively on two bounded-degree plane 6-spanners, one with maximum degree 12 and the other with maximum degree 9. Both spanners are subgraphs of the empty equilateral triangle Delaunay triangulation. First, in a weak routing model where the only information stored at each vertex is its neighbourhood, we show how to find a path between any two vertices of a 6-spanner of maximum degree 12, such that the path has length at most $95/\sqrt{3}$ times the straight-line distance between the vertices. In a slightly stronger model, where in addition to the neighbourhood of each vertex, we store $O(1)$ additional information, we show how to find a path that has length at most $15/\sqrt{3}$ times the Euclidean distance both in a 6-spanner of maximum degree 12 and a 6-spanner of maximum degree 9.
    With P. Bose, R. Fagerberg, and A. van Renssen.
    In Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012), pages 299–304, 2012.
    pdf Slides (pdf) Journal version 
    @inproceedings{bose2012competitive2,
  author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander},
  title={Competitive Routing on a Bounded-Degree Plane Spanner},
  booktitle={Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012)},
  year={2012},
  pages={299--304}
}

  22. Optimal bounds on Theta-graphs: more is not always better


    Abstract: We present improved upper and lower bounds for a large family of $\theta$-graphs. We show that $\theta$-graphs with $4k + 2$ cones ($k \geq 1$ and integer) have a spanning ratio of $1 + 2 \sin(\theta/2)$, where $\theta$ is $2 \pi / (4k + 2)$, and this spanning ratio is tight. We also show that $\theta$-graphs with $4k + 4$ cones have spanning ratio at least $1 + 2 \tan(\theta/2) + 4 \tan^2(\theta/2)$. This is somewhat surprising since, for equal values of $k$, the spanning ratio of $\theta$-graphs with $4k + 4$ cones is greater than that of $\theta$-graphs with $4k + 2$ cones, showing that increasing the number of cones can make the spanning ratio worse.
    With P. Bose, J.-L. De Carufel, P. Morin, and A. van Renssen.
    In Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012), pages 305–310, 2012.
    pdf Journal version 
    @inproceedings{bose2012optimal,
  author={Bose, Prosenjit and De Carufel, Jean-Lou and Morin, Pat and van Renssen, Andr\'e and Verdonschot, Sander},
  title={Optimal Bounds on {T}heta-Graphs: More is not Always Better},
  booktitle={Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012)},
  year={2012},
  pages={305--310}
}
  23. Evolution Strategies for Optimizing Rectangular Cartograms

    Evolution strategies for optimizing rectangular cartograms

    (presented)
    Abstract: A rectangular cartogram is a type of map where every region is a rectangle. The size of the rectangles is chosen such that their areas represent a geographic variable such as population or GDP. In recent years several algorithms for the automated construction of rectangular cartograms have been proposed, some of which are based on rectangular duals of the dual graph of the input map. In this paper we present a new approach to efficiently search within the exponentially large space of all possible rectangular duals. We employ evolution strategies that find rectangular duals which can be used for rectangular cartograms with correct adjacencies and (close to) zero cartographic error. This is a considerable improvement upon previous methods that have to either relax adjacency requirements or deal with larger errors. We present extensive experimental results for a large variety of data sets.
    With K. Buchin and B. Speckmann.
    In Proceedings of the 7th International Conference on Geographic Information Science (GIScience 2012), pages 29–42, 2012.
    pdf DOI Slides (pdf) 
    @inproceedings{buchin2012evolution,
  author={Buchin, Kevin and Speckmann, Bettina and Verdonschot, Sander},
  title={Evolution Strategies for Optimizing Rectangular Cartograms},
  booktitle={Proceedings of the 7th International Conference on Geographic Information Science (GIScience 2012)},
  year={2012},
  volume={7478},
  series={Lecture Notes in Computer Science},
  pages={29--42},
  doi={10.1007/978-3-642-33024-7_3}
}

  24. On plane constrained bounded-degree spanners

    (presented)
    Abstract: Let $P$ be a set of points in the plane and $S$ a set of non-crossing line segments with endpoints in $P$. The visibility graph of $P$ with respect to $S$, denoted $Vis(P,S)$, has vertex set $P$ and an edge for each pair of vertices $u,v$ in $P$ for which no line segment of $S$ properly intersects $uv$. We show that the constrained half-$\theta_6$-graph (which is identical to the constrained Delaunay graph whose empty visible region is an equilateral triangle) is a plane 2-spanner of $Vis(P,S)$. We then show how to construct a plane 6-spanner of $Vis(P,S)$ with maximum degree $6+c$, where $c$ is the maximum number of segments adjacent to a vertex.
    With P. Bose, R. Fagerberg, and A. van Renssen.
    In Proceedings of the 10th Latin American Symposium on Theoretical Informatics (LATIN 2012), pages 85–96, 2012.
    pdf DOI Journal version Slides (pdf) 
    @inproceedings{bose2012plane,
  author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander},
  title={On Plane Constrained Bounded-Degree Spanners},
  booktitle={Proceedings of the 10th Latin American Symposium on Theoretical Informatics (LATIN 2012)},
  year={2012},
  volume={7256},
  series={Lecture Notes in Computer Science},
  pages={85--96},
  doi={10.1007/978-3-642-29344-3_8}
}

  25. Competitive routing in the half-$\theta_6$-graph


    Abstract: We present a deterministic local routing scheme that is guaranteed to find a path between any pair of vertices in a half-$\theta_6$-graph whose length is at most $5/\sqrt{3}$ times the Euclidean distance between the pair of vertices. The half-$\theta_6$-graph is identical to the Delaunay triangulation where the empty region is an equilateral triangle. Moreover, we show that no local routing scheme can achieve a better competitive spanning ratio thereby implying that our routing scheme is optimal. This is somewhat surprising because the spanning ratio of the half-$\theta_6$-graph is 2. Since every triangulation can be embedded in the plane as a half-$\theta_6$-graph using $O(\log n)$ bits per vertex coordinate via Schnyder’s embedding scheme (SODA 1990), our result provides a competitive local routing scheme for every such embedded triangulation.
    With P. Bose, R. Fagerberg, and A. van Renssen.
    In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pages 1319–1328, 2012.
    pdf Journal version ACM 
    @inproceedings{bose2012competitive,
  author={Bose, Prosenjit and Fagerberg, Rolf and van Renssen, Andr\'e and Verdonschot, Sander},
  title={Competitive Routing in the Half-{$\theta_6$}-Graph},
  booktitle={Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)},
  year={2012},
  pages={1319--1328}
}

  26. On rectilinear partitions with minimum stabbing number


    Abstract: Let $S$ be a set of $n$ points in $\mathbb{R}^d$, and let $r$ be a parameter with $1 \leq r \leq n$. A rectilinear $r$-partition for $S$ is a collection $\Psi(S) := {(S_1, b_1), \dots , (S_t, b_t)}$, such that the sets $S_i$ form a partition of $S$, each $b_i$ is the bounding box of $S_i$, and $n/2r \leq |S_i| \leq 2n/r$ for all $1 \leq i \leq t$. The (rectilinear) stabbing number of $\Psi(S)$ is the maximum number of bounding boxes in $\Psi(S)$ that are intersected by an axis-parallel hyperplane $h$. We study the problem of finding an optimal rectilinear $r$-partition - a rectilinear partition with minimum stabbing number - for a given set $S$. We obtain the following results.
    - Computing an optimal partition is NP-hard already in $\mathbb{R}^2$.
    - There are point sets such that any partition with disjoint bounding boxes has stabbing number $\Omega(r^{1-1/d})$, while the optimal partition has stabbing number 2.
    - An exact algorithm to compute optimal partitions, running in polynomial time if $r$ is a constant, and a faster 2-approximation algorithm.
    - An experimental investigation of various heuristics for computing rectilinear $r$-partitions in $\mathbb{R}^2$.
    With M. de Berg, A. Khosravi, and V. van der Weele.
    In Proceedings of the 12th Algorithms and Data Structures Symposium (WADS 2011), pages 302–313, 2011.
    pdf DOI 
    @inproceedings{deberg2011rectilinear,
  author={de Berg, Mark and Khosravi, Amirali and Verdonschot, Sander and van der Weele, Vincent},
  title={On rectilinear partitions with minimum stabbing number},
  booktitle={Proceedings of the 12th Algorithms and Data Structures Symposium (WADS 2011)},
  year={2011},
  pages={302--313},
  doi={10.1007/978-3-642-22300-6_26}
}

  27. Making triangulations 4-connected using flips

    (presented)
    Abstract: We show that any triangulation on $n$ vertices can be transformed into a 4-connected one using at most $\lfloor(3n - 6)/5\rfloor$ edge flips. We also give an example of a triangulation that requires $\lceil(3n - 10)/5\rceil$ flips to be made 4-connected, showing that our bound is tight. Our result implies a new upper bound on the diameter of the flip graph of $5.2 n - 24.4$, improving on the bound of $6n -30$ by Mori et al.
    With P. Bose, D. Jansens, A. van Renssen, and M. Saumell.
    In Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), pages 241–247, 2011.
    pdf arXiv Slides (pdf) Journal version 
    @inproceedings{bose2011making,
  author={Bose, Prosenjit and Jansens, Dana and van Renssen, Andr\'e and Saumell, Maria and Verdonschot, Sander},
  title={Making triangulations 4-connected using flips},
  booktitle={Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011)},
  year={2011},
  pages={241--247}
}

  28. Optimizing regular edge labelings


    Abstract: A regular edge labeling (REL) of an irreducible triangulation $G$ uniquely defines a rectangular dual of $G$. Rectangular duals find applications in various areas: as floor plans of electronic chips, in architectural designs, as rectangular cartograms, or as treemaps. An irreducible triangulation can have many RELs and hence many rectangular duals. Depending on the specific application different duals might be desirable. In this paper we consider optimization problems on RELs and show how to find optimal or near-optimal RELs for various quality criteria. Along the way we give upper and lower bounds on the number of RELs.
    With K. Buchin and B. Speckmann.
    In Proceedings of the 18th International Symposium on Graph drawing (GD 2010), pages 117–128, 2011.
    pdf DOI Journal version 
    @inproceedings{buchin2011optimizing,
  author={Buchin, Kevin and Speckmann, Bettina and Verdonschot, Sander},
  title={Optimizing regular edge labelings},
  booktitle={Proceedings of the 18th International Symposium on Graph drawing (GD 2010)},
  year={2011},
  publisher={Springer-Verlag},
  volume={6502},
  series={Lecture Notes in Computer Science},
  address={Heidelberg},
  pages={117--128},
  doi={10.1007/978-3-642-18469-7_11}
}

Submitted Journal Conference Chapters Theses Talks

Chapters in Books

  1. A history of flips in combinatorial triangulations


    Abstract: Given two combinatorial triangulations, how many edge flips are necessary and sufficient to convert one into the other? This question has occupied researchers for over 75 years. We provide a comprehensive survey, including full proofs, of the various attempts to answer it.
    With P. Bose.
    In A. Márquez, P. Ramos, and J. Urrutia, editors, Proceedings of the XIV Spanish Meeting on Computational Geometry (EGC 2011), volume 7579 of Lecture Notes in Computer Science, pages 29–44. Springer Berlin Heidelberg, 2012.
    pdf arXiv DOI 
    @incollection{bose2012history,
  author={Bose, Prosenjit and Verdonschot, Sander},
  title={A History of Flips in Combinatorial Triangulations},
  booktitle={Proceedings of the XIV Spanish Meeting on Computational Geometry (EGC 2011)},
  year={2012},
  editor={M\'arquez, Alberto and Ramos, Pedro and Urrutia, Jorge},
  publisher={Springer Berlin Heidelberg},
  volume={7579},
  series={Lecture Notes in Computer Science},
  pages={29--44},
  doi={10.1007/978-3-642-34191-5_3}
}

Submitted Journal Conference Chapters Theses Talks

Theses

  1. Flips and spanners


    Abstract:

    In this thesis, we study two different graph problems.

    The first problem revolves around geometric spanners. Here, we have a set of points in the plane and we want to connect them with straight line segments, such that there is a path between each pair of points and these paths do not require large detours. If we achieve this, the resulting graph is called a spanner. We focus our attention on two graphs (the $\Theta$-graph and Yao-graph) that are constructed by connecting each point with its nearest neighbour in a number of cones. Although this construction is very straight-forward, it has proven challenging to fully determine the properties of the resulting graphs. We show that if the construction uses 5 cones, the resulting graphs are still spanners. This was the only number of cones for which this question remained unanswered. We also present a routing strategy (a way to decide where to go next, based only on our current location, its direct neighbourhood, and our destination) on the half-$\Theta_6$-graph, a variant of the graph with 6 cones. We show that our routing strategy avoids large detours: it finds a path whose length is at most a constant factor from the straight-line distance between the endpoints. Moreover, we show that this routing strategy is optimal.

    In the second part, we turn our attention to flips in triangulations. A flip is a simple operation that transforms one triangulation into another. It turns out that with enough flips, we can transform any triangulation into any other. But how many flips is enough? We present an improved upper bound of $5.2 n - 33.6$ on the maximum flip distance between any pair of triangulations with $n$ vertices. Along the way, we prove matching lower bounds on each step in the current algorithm, including a tight bound of $\lfloor(3n - 9)/5\rfloor$ flips needed to make a triangulation 4-connected. In addition, we prove tight $\Theta(n \log n)$ bounds on the number of flips required in several settings where the edges have unique labels.

    PhD thesis, Carleton University, 2015.
    pdf arXiv 
    @phdthesis{verdonschot2015flips,
  author={Verdonschot, Sander},
  title={Flips and Spanners},
  type={PhD thesis},
  school={Carleton University},
  year={2015}
}

  2. Optimizing regular edge labelings


    Abstract: A regular edge labeling of an irreducible triangulation $G$ uniquely defines a rectangular dual of $G$. Rectangular duals find applications in various areas: as floor plans of electronic chips, in architectural designs, as rectangular cartograms, or as treemaps. An irreducible triangulation can have many regular edge labelings and hence many rectangular duals. Depending on the specific application different duals might be desirable. In this thesis we consider optimization problems on regular edge labelings and show how to find optimal or near-optimal ones for various quality criteria. We evaluate our optimization methods by applying them to generate high quality rectangular cartograms. Furthermore, we show how to efficiently enumerate the regular edge labelings of an irreducible triangulation. Since the running time of the enumeration algorithm depends on the number of regular edge labelings, we also consider the maximal number of regular edge labelings an irreducible triangulation can have. We show that every irreducible triangulation with $n$ vertices has less than $O(4.6807^n)$ regular edge labelings and that there are irreducible triangulations with $\Omega(3.0426^n)$ regular edge labelings.
    Master’s thesis, Eindhoven University of Technology, 2010.
    pdf 
    @mastersthesis{verdonschot2010optimizing,
  author={Verdonschot, Sander},
  title={Optimizing Regular Edge Labelings},
  type={Master's thesis},
  school={Eindhoven University of Technology},
  year={2010}
}

Submitted Journal Conference Chapters Theses Talks

Invited Talks

  1. Flips in edge-labelled triangulations


    Abstract: Flips in tri­an­gu­la­tions have gen­er­ated a lot of in­ter­est over the past decades, but lit­tle at­ten­tion has been given to the move­ment of in­di­vid­ual edges dur­ing a se­quence of flips. We study this ques­tion by at­tach­ing a unique label to each edge of the tri­an­gu­la­tion. We give upper and lower bounds on the di­am­e­ter of the flip graph in this set­ting, for three kinds of tri­an­gu­la­tions: tri­an­gu­la­tions of a convex poly­gon, combinatorial triangulations and pseudo-tri­an­gu­la­tions.
    University of Waterloo, February 2016.
    Slides (pdf)

  2. Optimizing rectangular cartograms


    Abstract:

    A rectangular cartogram is a type of map where every region is a rectangle. The size of the rectangles is chosen such that their areas represent a geographic variable such as population or GDP. In recent years several algorithms for the automated construction of rectangular cartograms have been proposed, some of which are based on rectangular duals of the dual graph of the input map. A map can have many different rectangular duals, and depending on the specific application, different duals might be desirable.

    We present a new heuristic approach to efficiently search within the exponentially large space of all possible rectangular duals. We employ evolution strategies that find rectangular duals which can be used for rectangular cartograms with correct adjacencies and (close to) zero cartographic error. This is a considerable improvement upon previous methods that have to either relax adjacency requirements or deal with larger errors. We present extensive experimental results for a large variety of data sets.

    We also consider the maximal number of rectangular duals a map can have. We show that every map with n regions has less than $O(4.6807^n)$ rectangular duals and that there are maps with $\Omega(3.0426^n)$ rectangular duals.

    Tohoku University, January 2016.
    Slides (pdf)

  3. Flips in edge-labelled triangulations


    Abstract: Flips in triangulations have generated a lot of interest over the past decades, but little attention has been given to the movement of individual edges during a sequence of flips. We study this question by attaching a unique label to each edge of the triangulation. We give upper and lower bounds on the diameter of the flip graph in this setting, for two kinds of triangulations: triangulations of a convex polygon and combinatorial triangulations.
    Eindhoven University of Technology, June 2015.
    Slides (pdf)

  4. Flips in edge-labelled triangulations


    Abstract: Flips in triangulations have generated a lot of interest over the past decades, but little attention has been given to the movement of individual edges during a sequence of flips. We study this question by attaching a unique label to each edge of the triangulation. We give upper and lower bounds on the diameter of the flip graph in this setting, for two kinds of triangulations: triangulations of a convex polygon and pointed pseudo-triangulations.
    Université libre de Bruxelles, May 2015.
    Slides (pdf)

  5. Making triangulations 4-connected using flips


    Abstract: An edge flip is an operation that transforms one triangulation into another by replacing the diagonal of the quadrilateral formed by two adjacent triangles with the other possible diagonal. One of the most natural questions to ask, is whether this allows us to transform any given triangulation into any other (with the same number of vertices). This question was answered affirmatively by Wagner, when he introduced the flip operation in 1936. The next logical question then is, how many flips does this take? Careful analysis of Wagner’s proof shows that a number of flips quadratic in the number of vertices certainly suffices. However, more recently, Komuro showed that a linear number of flips suffices as well and Mori et al. improved this bound further to $6n - 30$ flips. Their algorithm consists of two steps; it first makes the given triangulation 4-connected and then transforms the result into a fixed canonical triangulation. We give a tight bound of $(3n - 7)/5$ flips on the first step and improve the second step to match the existing lower bound of $2n - 15$ flips, resulting in a new upper bound of $5.2n - 30.8$ flips.
    Eindhoven University of Technology, December 2011.
    Slides (pdf)

Submitted Journal Conference Chapters Theses Talks

Generated by Publy 1.3.  Last modified on 5 May 2019.