## Abstract

Let S be a planar n-point set. A triangulation for S is a maximal plane straight-line graph with vertex set S. The Voronoi diagram for S is the subdivision of the plane into cells such that each cell has the same nearest neighbors in S. Classically, both structures can be computed in O(n log n) time and O(n) space. We study the situation when the available workspace is limited: given a parameter s ∈ {1,..., n}, an s-workspace algorithm has read-only access to an input array with the points from S in arbitrary order, and it may use only O(s) additional words of Θ(log n) bits for reading and writing intermediate data. The output should then be written to a write-only structure. We describe a deterministic s-workspace algorithm for computing a triangulation of S in time O(n^{2}/s + n log n log s) and a randomized s-workspace algorithm for finding the Voronoi diagram of S in expected time O((n^{2}/s) log s + n log s log^{∗} s).

Original language | English |
---|---|

Title of host publication | Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings |

Editors | F. Dehne, J.-R. Sack, U. Stege |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 482-494 |

Number of pages | 13 |

ISBN (Electronic) | 9783319218403 |

ISBN (Print) | 9783319218397 |

DOIs | |

Publication status | Published - 1 Jan 2015 |

Externally published | Yes |

Event | 14th International Symposium on Algorithms and Data Structures (WADS 2015) - Victoria, Canada Duration: 5 Aug 2015 → 7 Aug 2015 Conference number: 14 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 9214 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 14th International Symposium on Algorithms and Data Structures (WADS 2015) |
---|---|

Abbreviated title | WADS 2015 |

Country | Canada |

City | Victoria |

Period | 5/08/15 → 7/08/15 |