Computing the maximum overlap of two convex polygons under translations

M. Berg, de, O. Cheong, O. Devillers, M.J. Kreveld, van, M. Teillaud

    Research output: Contribution to journalArticleAcademicpeer-review

    41 Citations (Scopus)


    Finding a vast array of applications, the list-ranking problem has emerged as one of the fundamental techniques in parallel algorithm design. Surprisingly, the best previously known algorithm to rank a list of n items on a reconfigurable mesh of size was running in O(log n ) time. It was open for more than 8 years to obtain a faster algorithm for this important problem. Our main contribution is to provide the first breakthrough: we propose a deterministic list-ranking algorithm that runs in O(log* n ) time as well as a randomized one running in O(1) expected time, both on a reconfigurable mesh of size . Our results open the door to a large number of efficient list-ranking-based algorithms on reconfigurable meshes.
    Original languageEnglish
    Pages (from-to)613-628
    Number of pages16
    JournalTheory of Computing Systems
    Issue number5
    Publication statusPublished - 1998


    Dive into the research topics of 'Computing the maximum overlap of two convex polygons under translations'. Together they form a unique fingerprint.

    Cite this