Memory-constrained algorithms for simple polygons

T. Asano, K. Buchin, M. Buchin, M. Korman, W. Mulzer, G. Rote, A. Schulz

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademic

13 Citaten (Scopus)
60 Downloads (Pure)


A constant-work-space algorithm has read-only access to an input array and may use only O(1) additional words of O(log n) bits, where n is the input size. We show how to triangulate a plane straight-line graph with n vertices in O(n2) time and constant workspace. We also consider the problem of preprocessing a simple n-gon P for shortest path queries, where P is given by the ordered sequence of its vertices. For this, we relax the space constraint to allow s words of work-space. After quadratic preprocessing, the shortest path between any two points inside P can be found in O(n2/s) time.
Originele taal-2Engels
TitelAbstracts 28th European Workshop on Computational Geometry (EuroCG 2012, Assisi, Italy, March 19-21, 2012)
Plaats van productiePerugia
UitgeverijUniversità degli Studi di Perugia
StatusGepubliceerd - 2012

Vingerafdruk Duik in de onderzoeksthema's van 'Memory-constrained algorithms for simple polygons'. Samen vormen ze een unieke vingerafdruk.

Citeer dit