Convex-hull algorithms: Implementation, testing, and experimentation

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Standard

Convex-hull algorithms : Implementation, testing, and experimentation. / Gamby, Ask Neve; Katajainen, Jyrki.

I: Algorithms, Bind 11, Nr. 12, 195, 2018, s. 1-27.

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Harvard

Gamby, AN & Katajainen, J 2018, 'Convex-hull algorithms: Implementation, testing, and experimentation', Algorithms, bind 11, nr. 12, 195, s. 1-27. https://doi.org/10.3390/a11120195

APA

Gamby, A. N., & Katajainen, J. (2018). Convex-hull algorithms: Implementation, testing, and experimentation. Algorithms, 11(12), 1-27. [195]. https://doi.org/10.3390/a11120195

Vancouver

Gamby AN, Katajainen J. Convex-hull algorithms: Implementation, testing, and experimentation. Algorithms. 2018;11(12):1-27. 195. https://doi.org/10.3390/a11120195

Author

Gamby, Ask Neve ; Katajainen, Jyrki. / Convex-hull algorithms : Implementation, testing, and experimentation. I: Algorithms. 2018 ; Bind 11, Nr. 12. s. 1-27.

Bibtex

@article{459f2a34736b46e0931b0ffdac0aa27c,
title = "Convex-hull algorithms: Implementation, testing, and experimentation",
abstract = "From a broad perspective, we study issues related to implementation, testing, and experimentation in the context of geometric algorithms. Our focus is on the effect of quality of implementation on experimental results. More concisely, we study algorithms that compute convex hulls for a multiset of points in the plane. We introduce several improvements to the implementations of the studied algorithms: PLANE-SWEEP, TORCH, QUICKHULL, and THROW-AWAY. With a new set of space-efficient implementations, the experimental results-in the integer-arithmetic setting-are different from those of earlier studies. From this, we conclude that utmost care is needed when doing experiments and when trying to draw solid conclusions upon them.",
keywords = "Algorithm, Algorithm engineering, Computational geometry, Convex hull, Experimentation, Implementation, Performance, Rectilinear convex hull, Robustness, Testing",
author = "Gamby, {Ask Neve} and Jyrki Katajainen",
year = "2018",
doi = "10.3390/a11120195",
language = "English",
volume = "11",
pages = "1--27",
journal = "Algorithms",
issn = "1999-4893",
publisher = "M D P I AG",
number = "12",

}

RIS

TY - JOUR

T1 - Convex-hull algorithms

T2 - Implementation, testing, and experimentation

AU - Gamby, Ask Neve

AU - Katajainen, Jyrki

PY - 2018

Y1 - 2018

N2 - From a broad perspective, we study issues related to implementation, testing, and experimentation in the context of geometric algorithms. Our focus is on the effect of quality of implementation on experimental results. More concisely, we study algorithms that compute convex hulls for a multiset of points in the plane. We introduce several improvements to the implementations of the studied algorithms: PLANE-SWEEP, TORCH, QUICKHULL, and THROW-AWAY. With a new set of space-efficient implementations, the experimental results-in the integer-arithmetic setting-are different from those of earlier studies. From this, we conclude that utmost care is needed when doing experiments and when trying to draw solid conclusions upon them.

AB - From a broad perspective, we study issues related to implementation, testing, and experimentation in the context of geometric algorithms. Our focus is on the effect of quality of implementation on experimental results. More concisely, we study algorithms that compute convex hulls for a multiset of points in the plane. We introduce several improvements to the implementations of the studied algorithms: PLANE-SWEEP, TORCH, QUICKHULL, and THROW-AWAY. With a new set of space-efficient implementations, the experimental results-in the integer-arithmetic setting-are different from those of earlier studies. From this, we conclude that utmost care is needed when doing experiments and when trying to draw solid conclusions upon them.

KW - Algorithm

KW - Algorithm engineering

KW - Computational geometry

KW - Convex hull

KW - Experimentation

KW - Implementation

KW - Performance

KW - Rectilinear convex hull

KW - Robustness

KW - Testing

UR - http://www.scopus.com/inward/record.url?scp=85059271551&partnerID=8YFLogxK

U2 - 10.3390/a11120195

DO - 10.3390/a11120195

M3 - Journal article

AN - SCOPUS:85059271551

VL - 11

SP - 1

EP - 27

JO - Algorithms

JF - Algorithms

SN - 1999-4893

IS - 12

M1 - 195

ER -

ID: 211107021