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.
Berg, de, M., Cheong, O., Devillers, O., Kreveld, van, M. J., & Teillaud, M. (1998). Computing the maximum overlap of two convex polygons under translations. Theory of Computing Systems, 31(5), 613-628. https://doi.org/10.1007/PL00005845