{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T18:19:41Z","timestamp":1649009981081},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1995,9]]},"abstract":"<jats:p> Let S be a set of m polygons in the plane with a total of n vertices. A translation order for S in direction [Formula: see text] is an order on the polygons such that no collisions occur if the polygons are moved one by one to infinity in direction [Formula: see text] according to this order. We show that S can be preprocessed in O(n log n) time into a data structure of size O(m) such that a translation order for a query direction can be computed in O(m) time, if it exists. It is also possible to test in O(log n) time whether a translation order exists, with a structure that uses O(n) storage. These results are achieved using new results on relative convex hulls and on embeddings with few vertices. Translation orders correspond to valid displaying orders for hidden surface removal with the painter\u2019s algorithm. Our technique can be used to generate displaying orders for polyhedral terrains, for parallel as well as perspective views. <\/jats:p>","DOI":"10.1142\/s0218195995000131","type":"journal-article","created":{"date-parts":[[2004,11,10]],"date-time":"2004-11-10T06:14:37Z","timestamp":1100067277000},"page":"221-242","source":"Crossref","is-referenced-by-count":2,"title":["TRANSLATION QUERIES FOR SETS OF POLYGONS"],"prefix":"10.1142","volume":"05","author":[{"given":"MARK DE","family":"BERG","sequence":"first","affiliation":[{"name":"Department of Computer Science, Utrecht University, P.O. Box 80.089 3508 TB Utrecht, The Netherlands"}]},{"given":"HAZEL","family":"EVERETT","sequence":"additional","affiliation":[{"name":"D\u00e9partement de Math\u00e9matiques et d\u2019Informatique, Universit\u00e9 du Qu\u00e9bec \u00e0 Montr\u00e9al, Case postale 8888, succursale A, Montr\u00e9al, Quebec Canada, H3C 3P8, Canada"}]},{"given":"HUBERT","family":"WAGENER","sequence":"additional","affiliation":[{"name":"FB Informatik, TU Berlin, FB 6\u20132, Franklinstr. 28\/29, D-1000 Berlin, Germany"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195995000131","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:30:45Z","timestamp":1565123445000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195995000131"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,9]]},"references-count":0,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1995,9]]}},"alternative-id":["10.1142\/S0218195995000131"],"URL":"https:\/\/doi.org\/10.1142\/s0218195995000131","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,9]]}}}