A Parallel Algorithm for Partitioning a Point Set to Minimize the Maximum of Diameters |
| |
| Affiliation: | 1. Global Academy for Agriculture and Food Security, University of Edinburgh Easter Bush Campus, Midlothian EH25 9RG, United Kingdom;2. Royal (Dick) School of Veterinary Studies and Roslin Institute University of Edinburgh Easter Bush Campus, Midlothian EH25 9RG, United Kingdom;1. Alan G. MacDiarmid Institute, College of Chemistry, Jilin University, Changchun 130012, China;2. School of Materials Science and Engineering, China University of Petroleum, Qingdao 266580, China;1. Department of Physics, Southern University of Science and Technology, Shenzhen 518055, China;2. Departamento de Física, ICE, Universidade Federal de Juiz de Fora, Juiz de Fora, CEP: 36036-330, MG, Brazil;3. Department of Mathematical Analysis, Tomsk State Pedagogical University, 634061, Kievskaya St. 60, Tomsk, Russia;4. National Research Tomsk State University, Lenin Av. 36, 634050 Tomsk, Russia;1. University of Louisville, Louisville, KY 40292, United States of America;2. Alfréd Rényi Mathematical Institute, Budapest, Hungary |
| |
| Abstract: | Given a set S of n points in the plane, we consider the problem of partitioning S into two subsets such that the maximum of their diameters is minimized. We present a parallel algorithm to solve this problem that runs in time O(log n) using the CREW PRAM with 0(n2) processors. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
