Translation queries for sets of polygons

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

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer 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.
    Originele taal-2Engels
    Pagina's (van-tot)221-242
    TijdschriftInternational Journal of Computational Geometry and Applications
    Nummer van het tijdschrift3
    StatusGepubliceerd - 1995

    Vingerafdruk Duik in de onderzoeksthema's van 'Translation queries for sets of polygons'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit