Zobrazeno 1 - 10
of 95
pro vyhledávání: '"Verdonschot, Sander"'
Autor:
De Carufel, Jean-Lou, Dumitrescu, Adrian, Meulemans, Wouter, Ophelders, Tim, Pennarun, Claire, Tóth, Csaba D, Verdonschot, Sander
Publikováno v:
Journal of Computational Geometry 11(2) (2021). Special Issue of Selected Papers from SoCG 2019
We study several problems concerning convex polygons whose vertices lie in a Cartesian product of two sets of $n$ real numbers (for short, \emph{grid}). First, we prove that every such grid contains $\Omega(\log n)$ points in convex position and that
Externí odkaz:
http://arxiv.org/abs/1812.11332
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 requ
Externí odkaz:
http://arxiv.org/abs/1804.07150
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 se
Externí odkaz:
http://arxiv.org/abs/1803.02979
An $\omega$-wedge is the closed set of points contained between two rays that are emanating from a single point (the apex), and are separated by an angle $\omega < \pi$. Given a convex polygon $P$, we place the $\omega$-wedge such that $P$ is inside
Externí odkaz:
http://arxiv.org/abs/1801.02162
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 con
Externí odkaz:
http://arxiv.org/abs/1710.08060
Autor:
Barba, Luis, Cardinal, Jean, Korman, Matias, Langerman, Stefan, van Renssen, André, Roeloffzen, Marcel, Verdonschot, Sander
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-of
Externí odkaz:
http://arxiv.org/abs/1708.09080
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 set M of monitored vertices is built as follows: at first, M contains only the vertices of S and their direct
Externí odkaz:
http://arxiv.org/abs/1707.02760
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 $Vis(P,S)$, has vertex set $P$ and an edge for each pair of vertices $u,v$ in $
Externí odkaz:
http://arxiv.org/abs/1704.03596
Autor:
Bonichon, Nicolas, Bose, Prosenjit, Carmi, Paz, Kostitsyna, Irina, Lubiw, Anna, Verdonschot, Sander
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 Gudmu
Externí odkaz:
http://arxiv.org/abs/1608.08892
Autor:
Bose, Prosenjit, Verdonschot, Sander
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-triang
Externí odkaz:
http://arxiv.org/abs/1512.01485