DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2016.30

Time-Space Trade-offs for Triangulating a Simple Polygon

Authors: Boris Aronov, Matias Korman, Simon Pratt, André van Renssen, and Marcel Roeloffzen

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract

An s-workspace algorithm is an algorithm that has read-only access to the values of the input, write-only access to the output, and only uses O(s) additional words of space. We give a randomized s-workspace algorithm for triangulating a simple polygon P of n vertices, for any s up to n. The algorithm runs in O(n^2/s+n(log s)log^5(n/s)) expected time using O(s) variables, for any s up to n. In particular, the algorithm runs in O(n^2/s) expected time for most values of s.

Cite as

Boris Aronov, Matias Korman, Simon Pratt, André van Renssen, and Marcel Roeloffzen. Time-Space Trade-offs for Triangulating a Simple Polygon. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 30:1-30:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.SWAT.2016.30,
  author =	{Aronov, Boris and Korman, Matias and Pratt, Simon and van Renssen, André and Roeloffzen, Marcel},
  title =	{{Time-Space Trade-offs for Triangulating a Simple Polygon}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{30:1--30:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.30},
  URN =		{urn:nbn:de:0030-drops-60522},
  doi =		{10.4230/LIPIcs.SWAT.2016.30},
  annote =	{Keywords: simple polygon, triangulation, shortest path, time-space trade-off}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2016.28

Two Approaches to Building Time-Windowed Geometric Data Structures

Authors: Timothy M. Chan and Simon Pratt

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

Abstract

Given a set of geometric objects each associated with a time value, we wish to determine whether a given property is true for a subset of those objects whose time values fall within a query time window. We call such problems time-windowed decision problems, and they have been the subject of much recent attention, for instance studied by Bokal, Cabello, and Eppstein [SoCG 2015]. In this paper, we present new approaches to this class of problems that are conceptually simpler than Bokal et al.'s, and also lead to faster algorithms. For instance, we present algorithms for preprocessing for the time-windowed 2D diameter decision problem in O(n log n) time and the time-windowed 2D convex hull area decision problem in O(n alpha(n) log n) time (where alpha is the inverse Ackermann function), improving Bokal et al.'s O(n log^2 n) and O(n log n loglog n) solutions respectively. Our first approach is to reduce time-windowed decision problems to a generalized range successor problem, which we solve using a novel way to search range trees. Our other approach is to use dynamic data structures directly, taking advantage of a new observation that the total number of combinatorial changes to a planar convex hull is near linear for any FIFO update sequence, in which deletions occur in the same order as insertions. We also apply these approaches to obtain the first O(n polylog n) algorithms for the time-windowed 3D diameter decision and 2D orthogonal segment intersection detection problems.

Cite as

Timothy M. Chan and Simon Pratt. Two Approaches to Building Time-Windowed Geometric Data Structures. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.SoCG.2016.28,
  author =	{Chan, Timothy M. and Pratt, Simon},
  title =	{{Two Approaches to Building Time-Windowed Geometric Data Structures}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.28},
  URN =		{urn:nbn:de:0030-drops-59201},
  doi =		{10.4230/LIPIcs.SoCG.2016.28},
  annote =	{Keywords: time window, geometric data structures, range searching, dynamic convex hull}
}

Search Results

Documents authored by Pratt, Simon

Time-Space Trade-offs for Triangulating a Simple Polygon

Abstract

Cite as

Two Approaches to Building Time-Windowed Geometric Data Structures

Abstract

Cite as

Thanks for your feedback!

Could not send message