Convex-hull algorithms: Implementation, testing, and experimentation

Ask Neve Gamby; Jyrki Katajainen

doi:10.3390/a11120195

Convex-hull algorithms: Implementation, testing, and experimentation

Ask Neve Gamby, Jyrki Katajainen^*

^*Corresponding author for this work

Department of Computer Science

8 Citations (Scopus)

59 Downloads (Pure)

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.

Original language	English
Article number	195
Journal	Algorithms
Volume	11
Issue number	12
Pages (from-to)	1-27
ISSN	1999-4893
DOIs	https://doi.org/10.3390/a11120195
Publication status	Published - 2018

Keywords

Algorithm
Algorithm engineering
Computational geometry
Convex hull
Experimentation
Implementation
Performance
Rectilinear convex hull
Robustness
Testing

Access to Document

10.3390/a11120195Licence: CC BY

algorithms-11-00195-v3Final published version, 494 KBLicence: CC BY

Cite this

@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",

}

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

SN - 1999-4893

VL - 11

SP - 1

EP - 27

JO - Algorithms

JF - Algorithms

IS - 12

M1 - 195

ER -

Convex-hull algorithms: Implementation, testing, and experimentation

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this