caa a22 4500 465821138 CHVBK 20180323112136.0 cr unu---uuuuu 170327e19900901xx s 000 0 eng 10.1007/BF01931655 doi (NATIONALLICENCE)springer-10.1007/BF01931655 A sublogarithmic convex hull algorithm [Elektronische Daten] [Per-Olof Fjällström, Jyrki Katajainen, Christos Levcopoulos, Ola Petersson] We present a parallel algorithm for finding the convex hull of a sorted set of points in the plane. Our algorithm runs inO(logn/log logn) time usingO(n log logn/logn) processors in theCommon crcw pram computational model, which is shown to be time and cost optimal. The algorithm is based onn 1/3 divide-and-conquer and uses a simple pointer-based data structure. BIT Foundations, 1990 F.1.2 nationallicence F.2.2 nationallicence Parallel algorithms nationallicence pram nationallicence computational geometry nationallicence divide-and-conquer nationallicence convex hull problem nationallicence Fjällström Per-Olof Department of Computer and Information Science, Linköping University, S-58183, Linköping, Sweden aut Katajainen Jyrki Department of Computer Science, University of Turku, Lemminkäisenkatu 14 A, SF-20 520, Turku, Finland aut Levcopoulos Christos Algorithm Theory Group, Department of Computer Science, Lund University, Box 118, S-221 00, Lund, Sweden aut Petersson Ola Algorithm Theory Group, Department of Computer Science, Lund University, Box 118, S-221 00, Lund, Sweden aut BIT Numerical Mathematics Kluwer Academic Publishers 30/3(1990-09-01), 378-384 0006-3835 30:3<378 1990 30 10543 https://doi.org/10.1007/BF01931655 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01931655 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Fjällström Per-Olof Department of Computer and Information Science, Linköping University, S-58183, Linköping, Sweden aut NATIONALLICENCE 700 1- Katajainen Jyrki Department of Computer Science, University of Turku, Lemminkäisenkatu 14 A, SF-20 520, Turku, Finland aut NATIONALLICENCE 700 1- Levcopoulos Christos Algorithm Theory Group, Department of Computer Science, Lund University, Box 118, S-221 00, Lund, Sweden aut NATIONALLICENCE 700 1- Petersson Ola Algorithm Theory Group, Department of Computer Science, Lund University, Box 118, S-221 00, Lund, Sweden aut NATIONALLICENCE 773 0- BIT Numerical Mathematics Kluwer Academic Publishers 30/3(1990-09-01), 378-384 0006-3835 30:3<378 1990 30 10543 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer