{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:24:24Z","timestamp":1760441064933},"reference-count":19,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:p> Let P be a simple polygon of n vertices and let S be a set of N points lying in the interior of P. A geodesic diskGD(p,r) with center p and radius r is the set of points in P that have a geodesic distance \u2264 r from p (where the geodesic distance is the length of the shortest polygonal path connection that lies in P). In this paper we present an output sensitive algorithm for finding all N geodesic disks centered at the points of S, for a given value of r. Our algorithm runs in [Formula: see text] time, for some constant c and output size k. It is the basis of a cluster reporting algorithm where geodesic distances are used. <\/jats:p>","DOI":"10.1142\/s0218195911003822","type":"journal-article","created":{"date-parts":[[2012,2,13]],"date-time":"2012-02-13T10:01:28Z","timestamp":1329127288000},"page":"595-608","source":"Crossref","is-referenced-by-count":4,"title":["GEODESIC DISKS AND CLUSTERING IN A SIMPLE POLYGON"],"prefix":"10.1142","volume":"21","author":[{"given":"MAGDALENE G.","family":"BORGELT","sequence":"first","affiliation":[{"name":"European Centre for Soft Computing, Mieres, Asturias, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MARC","family":"VAN KREVELD","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science, Utrecht University, the Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JUN","family":"LUO","sequence":"additional","affiliation":[{"name":"Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,6]]},"reference":[{"key":"rf1","unstructured":"P. K.\u00a0Agarwal, Handbook of Discrete and Computational Geometry, 2nd edn., eds. J. E.\u00a0Goodman and J.\u00a0O'Rourke (Chapman & Hall\/CRC, Boca Raton, 2004)\u00a0pp. 809\u2013838."},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/223\/03131"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01553882"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01377183"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1048"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574012"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840360"},{"key":"rf14","unstructured":"D.\u00a0Halperin, Handbook of Discrete and Computational Geometry, 2nd edn., eds. J. E.\u00a0Goodman and J.\u00a0ORourke (Chapman & Hall\/CRC, Boca Raton, 2004)\u00a0pp. 529\u2013562."},{"key":"rf15","volume-title":"Data Mining: Concepts and Techniques","author":"Han J.","year":"2001"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1123-0"},{"key":"rf17","volume-title":"Clustering Algorithms","author":"Hartigan J.","year":"1975"},{"key":"rf18","volume-title":"Algorithms for Clustering Data","author":"Jain A.","year":"1988"},{"key":"rf20","first-page":"478","volume":"31","author":"Lee D.","journal-title":"IEEE Trans. Comput. C"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00190-A"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.4324\/9780203468029"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187751"},{"key":"rf24","volume-title":"Geographic Information Analysis","author":"O'Sullivan D.","year":"2003"},{"key":"rf25","first-page":"9","volume":"3","author":"Toussaint G.","journal-title":"Revue D'Intelligence Artificielle"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195911003822","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:30:59Z","timestamp":1565123459000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195911003822"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":19,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2012,4,6]]},"published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.1142\/S0218195911003822"],"URL":"https:\/\/doi.org\/10.1142\/s0218195911003822","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12]]}}}