{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T10:02:28Z","timestamp":1769076148672,"version":"3.49.0"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,6,13]],"date-time":"2018-06-13T00:00:00Z","timestamp":1528848000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2018,6,13]]},"abstract":"<jats:p>In the limited workspace model, we consider algorithms whose input resides in read-only memory and that use only a constant or sublinear amount of writable memory to accomplish their task. We survey recent results in computational geometry that fall into this model and that strive to achieve the lowest possible running time. In addition to discussing the state of the art, we give some illustrative examples and mention open problems for further research.<\/jats:p>","DOI":"10.1145\/3232679.3232692","type":"journal-article","created":{"date-parts":[[2018,6,13]],"date-time":"2018-06-13T13:02:37Z","timestamp":1528894957000},"page":"77-94","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Computational Geometry Column 67"],"prefix":"10.1145","volume":"49","author":[{"given":"Bahareh","family":"Banyassady","sequence":"first","affiliation":[{"name":"Freie Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matias","family":"Korman","sequence":"additional","affiliation":[{"name":"Tohoku University, Sendai, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wolfgang","family":"Mulzer","sequence":"additional","affiliation":[{"name":"Freie Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,6,13]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proc. 25th Canad. Conf. Comput. Geom. (CCCG)","author":"Abrahamsen M.","year":"2013"},{"key":"e_1_2_1_2_1","first-page":"208","volume-title":"Proc. 31st Int. Sympos. Comput. Geom. (SoCG)","author":"Abrahamsen M.","year":"2015"},{"key":"e_1_2_1_3_1","first-page":"15","volume-title":"Proc. 24th Annu. European Sympos. Algorithms (ESA)","author":"Abrahamsen M.","year":"2016"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008736"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-62389-4_1"},{"key":"e_1_2_1_6_1","first-page":"12","volume-title":"Proc. 15th Scand. Symp. Work. Alg. Theo. (SWAT)","author":"Aronov B.","year":"2016"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1540612"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92182-0_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2013.11.004"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38236-9_4"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40104-6_6"},{"issue":"1","key":"e_1_2_1_12_1","first-page":"68","article-title":"Constant-work-space algorithms for geometric problems","volume":"2","author":"Asano T.","year":"2011","journal-title":"J. Comput. Geom."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00240"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"F. Aurenhammer R. Klein and D.-T. Lee. Voronoi Diagrams and Delaunay Triangulations. World Scienti c Publishing 2013.   F. Aurenhammer R. Klein and D.-T. Lee. Voronoi Diagrams and Delaunay Triangulations. World Scienti c Publishing 2013.","DOI":"10.1142\/8685"},{"key":"e_1_2_1_15_1","first-page":"2018","volume-title":"Proc. 17th Int. Symp. Experimental Algorithms (SEA)","author":"Baffier J.-F."},{"key":"e_1_2_1_16_1","first-page":"319","volume-title":"Proc. 11th Workshop Alg. Comp. (WALCOM)","author":"Bahoo Y.","year":"2017"},{"issue":"14","key":"e_1_2_1_17_1","first-page":"1932","article-title":"A hybrid metaheuristic strategy for covering with wireless devices","volume":"18","author":"Bajuelos A. L.","year":"1906","journal-title":"J. UCS"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21398-9_28"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-77404-6_9"},{"key":"e_1_2_1_20_1","first-page":"14","volume-title":"Proc. 34th Sympos. Theoret. Aspects Comput. Sci. (STACS)","author":"Banyassady B.","year":"2017"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9893-5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2014.04.001"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220017"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"M. de Berg O. Cheong M. van Kreveld and M. Overmars. Computational Geometry: Algo- rithms and Applications. Springer-Verlag Berlin third edition 2008.   M. de Berg O. Cheong M. van Kreveld and M. Overmars. Computational Geometry: Algo- rithms and Applications. Springer-Verlag Berlin third edition 2008.","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997854"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/646389.690520"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1646483.1646578"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1275-6"},{"key":"e_1_2_1_29_1","first-page":"911","volume-title":"Proc. 19th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA)","author":"Chan T. M.","year":"2008"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2010.04.005"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634148"},{"issue":"5","key":"e_1_2_1_32_1","first-page":"524","article-title":"Triangulating a simple polygon in linear time","volume":"6","author":"Chazelle B.","year":"1991","journal-title":"Discrete Comput. Geom."},{"issue":"5","key":"e_1_2_1_33_1","first-page":"421","article-title":"Applications of random sampling in computational geometry","volume":"4","author":"Clarkson K. L.","year":"1989","journal-title":"II. Discrete Comput. Geom."},{"key":"e_1_2_1_34_1","first-page":"168","volume-title":"Proc. 33rd European Workshop Comput. Geom. (EWCG)","author":"Cleve J.","year":"2017"},{"key":"e_1_2_1_35_1","first-page":"295","volume-title":"Proc. 22nd Annu. European Sympos. Algorithms (ESA)","author":"Darwish O.","year":"2014"},{"key":"e_1_2_1_36_1","first-page":"461","volume-title":"J.-R","author":"Eppstein D."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90062-5"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.08.048"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/1214709"},{"key":"e_1_2_1_40_1","volume-title":"Cambridge University Press","author":"Goldreich O.","year":"2008"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582157"},{"issue":"2","key":"e_1_2_1_42_1","first-page":"45","article-title":"Shortest path in a polygon using sublinear space","volume":"7","author":"Har-Peled S.","year":"2016","journal-title":"J. Comput. Geom."},{"key":"e_1_2_1_43_1","first-page":"235","volume-title":"Ian Munro on the Occasion of His 66th Birthday","author":"He M.","year":"2013"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217058"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30538-5_3"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(73)90020-3"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01937271"},{"key":"e_1_2_1_48_1","unstructured":"D. Knuth. The Art of Computer Programming: Fundamental Algorithms volume 1. Addison- Wesley Redwood City CA USA 3rd edition 1997.   D. Knuth. The Art of Computer Programming: Fundamental Algorithms volume 1. Addison- Wesley Redwood City CA USA 3rd edition 1997."},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","unstructured":"M. Korman W. Mulzer A. van Renssen M. Roelo zen P. Seiferth and Y. Stein. Time-space trade-o s for triangulations and Voronoi diagrams. Comput. Geom. page available online 2017.  M. Korman W. Mulzer A. van Renssen M. Roelo zen P. Seiferth and Y. Stein. Time-space trade-o s for triangulations and Voronoi diagrams. Comput. Geom. page available online 2017.","DOI":"10.1016\/j.comgeo.2017.01.001"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1676031"},{"issue":"2","key":"e_1_2_1_51_1","first-page":"98","article-title":"On nding the convex hull of a simple polygon","volume":"12","author":"Lee D.-T.","year":"1983","journal-title":"International Journal of Parallel Programming"},{"key":"e_1_2_1_52_1","first-page":"848","volume-title":"J. E. Goodman, J. O'Rourke, and C","author":"Mitchell J. S. B."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/3092586"},{"key":"e_1_2_1_55_1","first-page":"12","volume-title":"Proc. 28th Annu. Internat. Sympos. Algorithms Comput. (ISAAC)","author":"Oh E.","year":"2017"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"e_1_2_1_58_1","first-page":"96","article-title":"The method of forcing for nondeterministic automata","volume":"33","author":"Szelepcs\u00e9nyi R.","year":"1987","journal-title":"Bulletin of the EATCS"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3232679.3232692","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3232679.3232692","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:41:32Z","timestamp":1750282892000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3232679.3232692"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,13]]},"references-count":58,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,6,13]]}},"alternative-id":["10.1145\/3232679.3232692"],"URL":"https:\/\/doi.org\/10.1145\/3232679.3232692","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2018,6,13]]},"assertion":[{"value":"2018-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}