caa a22 4500 46582157X CHVBK 20180323112137.0 cr unu---uuuuu 170327e19900601xx s 000 0 eng 10.1007/BF02017351 doi (NATIONALLICENCE)springer-10.1007/BF02017351 An efficient and numerically correct algorithm for the 2D convex hull problem [Elektronische Daten] [Thomas Kao, Gary Knott] An efficient and numerically correct program called FastHull for computing the convex hulls of finite point sets in the plane is presented. It is based on the Akl-Toussaint algorithm and the MergeHull algorithm. Numerical correctness of the FastHull procedure is ensured by using special routines for interval arithmetic and multiple precision arithmetic. The FastHull algorithm guaranteesO(N logN) running time in the worst case and has linear time performance for many kinds of input patterns. It appears that the FastHull algorithm runs faster than any currently known 2D convex hull algorithm for many input point patterns. BIT Foundations, 1990 I.3.5 nationallicence G.1.0 nationallicence F.2.2 nationallicence Bucketing Techniques nationallicence Convex Hulls nationallicence Computational Geometry nationallicence Numerical Correctness nationallicence Point Elimination Techniques nationallicence Kao Thomas Dept. of Computer Science, University of Maryland, 20742, College Park, MD, USA aut Knott Gary Dept. of Computer Science, University of Maryland, 20742, College Park, MD, USA aut BIT Kluwer Academic Publishers 30/2(1990-06-01), 311-331 0006-3835 30:2<311 1990 30 10543 https://doi.org/10.1007/BF02017351 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02017351 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Kao Thomas Dept. of Computer Science, University of Maryland, 20742, College Park, MD, USA aut NATIONALLICENCE 700 1- Knott Gary Dept. of Computer Science, University of Maryland, 20742, College Park, MD, USA aut NATIONALLICENCE 773 0- BIT Kluwer Academic Publishers 30/2(1990-06-01), 311-331 0006-3835 30:2<311 1990 30 10543 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer