{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:36:31Z","timestamp":1758274591293},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2005,8]]},"abstract":"<jats:p> We consider the problem of computing large connected regions in a triangulated terrain of size n for which the normals of the triangles deviate by at most some small fixed angle. In previous work an exact near-quadratic algorithm was presented, but only a heuristic implementation with no guarantee was practicable. We present a new approximation algorithm for the problem which runs in O(n\/\u220a<jats:sup>2<\/jats:sup>) time and\u2014apart from giving a guarantee on the quality of the produced solution\u2014has been implemented and shows good performance on real data sets representing fracture surfaces consisting of around half a million triangles. Further we present a simple approximation algorithm for a related problem: given a set of n points in the plane, determine the placement of the unit disk which contains most points. This algorithm runs in linear time as well. <\/jats:p>","DOI":"10.1142\/s0218195905001750","type":"journal-article","created":{"date-parts":[[2005,8,22]],"date-time":"2005-08-22T11:56:45Z","timestamp":1124711805000},"page":"379-401","source":"Crossref","is-referenced-by-count":3,"title":["FINDING PLANAR REGIONS IN A TERRAIN \u2013 IN PRACTICE AND WITH A GUARANTEE"],"prefix":"10.1142","volume":"15","author":[{"given":"STEFAN","family":"FUNKE","sequence":"first","affiliation":[{"name":"Max-Plank-Institut f\u00fcr Informatik, Stuhlsatzenhausweg 85, Saarbr\u00fccken, 66123, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"THEOCHARIS","family":"MALAMATOS","sequence":"additional","affiliation":[{"name":"Max-Plank-Institut f\u00fcr Informatik, Stuhlsatzenhausweg 85, Saarbr\u00fccken, 66123, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"RAHUL","family":"RAY","sequence":"additional","affiliation":[{"name":"Max-Plank-Institut f\u00fcr Informatik, Stuhlsatzenhausweg 85, Saarbr\u00fccken, 66123, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2002.11.004"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1002\/1521-4052(200210)33:10<621::AID-MAWE621>3.0.CO;2-X"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45749-6_8"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_27"},{"key":"rf6","unstructured":"D.\u00a0Chen, M.\u00a0Smid and B.\u00a0Xu, Proc. 10th Ann. European Symp. Algorithms, Lecture Notes Computer Science (Springer-Verlag)\u00a0pp. 284\u2013296."},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0110-y"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90004-V"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1036"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02238188"},{"key":"rf14","volume-title":"LEDA: A Platform for Combinatorial and Geometric Computing","author":"Mehlhorn K.","year":"1999"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195905001750","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:29:28Z","timestamp":1565137768000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195905001750"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,8]]},"references-count":11,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,8]]}},"alternative-id":["10.1142\/S0218195905001750"],"URL":"https:\/\/doi.org\/10.1142\/s0218195905001750","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,8]]}}}