Time-space trade-offs for triangulating a simple polygon

Boris Aronov, Matias Korman, Simon Pratt, André Van Renssen, Marcel Roeloffzen

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)
2 Downloads (Pure)

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 ∈ O(n). The algorithm runs in O(n2/s + n(log s) log5 (n/s)) expected time using O(s) variables, for any s ∈ O(n). In particular, when s ∈ O(n/log n log5 log n) algorithm runs in O(n2/s) expected time.

Original languageEnglish
Title of host publication15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016
EditorsR. Pagh
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Chapter12
ISBN (Electronic)9783959770118
DOIs
Publication statusPublished - 1 Jun 2016
Externally publishedYes
Event15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) - Reykjavik, Iceland
Duration: 22 Jun 201624 Jun 2016
Conference number: 15

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume53
ISSN (Print)1868-8969

Conference

Conference15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Abbreviated titleSWAT 2016
CountryIceland
CityReykjavik
Period22/06/1624/06/16

Keywords

  • Shortest path
  • Simple polygon
  • Time-space trade-off
  • Triangulation

Cite this