3 Search Results for "Verdonschot, Sander"

Document

DOI: 10.4230/LIPIcs.SoCG.2019.22

Convex Polygons in Cartesian Products

Authors: Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth, and Sander Verdonschot

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

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 N), and obtain a tight lower bound of Omega(log^{d-1}n) 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.

Cite as

Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth, and Sander Verdonschot. Convex Polygons in Cartesian Products. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{decarufel_et_al:LIPIcs.SoCG.2019.22,
  author =	{De Carufel, Jean-Lou and Dumitrescu, Adrian and Meulemans, Wouter and Ophelders, Tim and Pennarun, Claire and T\'{o}th, Csaba D. and Verdonschot, Sander},
  title =	{{Convex Polygons in Cartesian Products}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.22},
  URN =		{urn:nbn:de:0030-drops-104267},
  doi =		{10.4230/LIPIcs.SoCG.2019.22},
  annote =	{Keywords: Erd\H{o}s-Szekeres theorem, Cartesian product, convexity, polyhedron, recursive construction, approximation algorithm}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2018.14

Improved Bounds for Guarding Plane Graphs with Edges

Authors: Ahmad Biniaz, Prosenjit Bose, Aurélien Ooms, and Sander Verdonschot

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

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 2n/5 edges, then extend this approach with a deeper analysis to yield an improved bound of 3n/8 edges for any plane graph. 2) We prove that there exists an edge guard set of G with at most n/(3) + alpha/9 edges, where alpha is the number of quadrilateral faces in G. This improves the previous bound of 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 n/(3) edges suffice, removing the dependence on alpha.

Cite as

Ahmad Biniaz, Prosenjit Bose, Aurélien Ooms, and Sander Verdonschot. Improved Bounds for Guarding Plane Graphs with Edges. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{biniaz_et_al:LIPIcs.SWAT.2018.14,
  author =	{Biniaz, Ahmad and Bose, Prosenjit and Ooms, Aur\'{e}lien and Verdonschot, Sander},
  title =	{{Improved Bounds for Guarding Plane Graphs with Edges}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{14:1--14:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.14},
  URN =		{urn:nbn:de:0030-drops-88403},
  doi =		{10.4230/LIPIcs.SWAT.2018.14},
  annote =	{Keywords: edge guards, graph coloring, four-color theorem}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2017.18

Routing on the Visibility Graph

Authors: Prosenjit Bose, Matias Korman, André van Renssen, and Sander Verdonschot

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

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 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 two 1-local O(1)-memory routing algorithms on 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 routing algorithms, our routing algorithms do not require us to compute a plane subgraph of the visibility graph in order to route on it.

Cite as

Prosenjit Bose, Matias Korman, André van Renssen, and Sander Verdonschot. Routing on the Visibility Graph. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 18:1-18:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bose_et_al:LIPIcs.ISAAC.2017.18,
  author =	{Bose, Prosenjit and Korman, Matias and van Renssen, Andr\'{e} and Verdonschot, Sander},
  title =	{{Routing on the Visibility Graph}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{18:1--18:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.18},
  URN =		{urn:nbn:de:0030-drops-82224},
  doi =		{10.4230/LIPIcs.ISAAC.2017.18},
  annote =	{Keywords: Routing, constraints, visibility graph, Theta-graph}
}

Refine by Author
3 Verdonschot, Sander
2 Bose, Prosenjit
1 Biniaz, Ahmad
1 De Carufel, Jean-Lou
1 Dumitrescu, Adrian
Show More...

Refine by Classification
2 Theory of computation → Computational geometry
1 Mathematics of computing → Graph theory

Refine by Keyword
1 Cartesian product
1 Erdős-Szekeres theorem
1 Routing
1 Theta-graph
1 approximation algorithm
Show More...

Refine by Type
3 document

Refine by Publication Year
1 2017
1 2018
1 2019

3 Search Results for "Verdonschot, Sander"

Convex Polygons in Cartesian Products

Abstract

Cite as

Improved Bounds for Guarding Plane Graphs with Edges

Abstract

Cite as

Routing on the Visibility Graph

Abstract

Cite as

Thanks for your feedback!

Could not send message