Translation queries for sets of polygons

M. Berg, de, H. Everett, H. Wagener

    Research output: Contribution to journalArticleAcademicpeer-review


    Let S be a set of m polygons in the plane with a total of n vertices. A translation order for S in direction is an order on the polygons such that no collisions occur if the polygons are moved one by one to infinity in direction 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’s algorithm. Our technique can be used to generate displaying orders for polyhedral terrains, for parallel as well as perspective views.
    Original languageEnglish
    Pages (from-to)221-242
    JournalInternational Journal of Computational Geometry and Applications
    Issue number3
    Publication statusPublished - 1995


    Dive into the research topics of 'Translation queries for sets of polygons'. Together they form a unique fingerprint.

    Cite this