Convex-hull algorithms: Implementation, testing, and experimentation

Ask Neve Gamby, Jyrki Katajainen*

*Corresponding author for this work

    Research output: Contribution to journalJournal articleResearchpeer-review

    935 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 languageEnglish
    Article number195
    JournalAlgorithms
    Volume11
    Issue number12
    Number of pages27
    ISSN1017-1398
    DOIs
    Publication statusPublished - 1 Dec 2018

    Keywords

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

    Fingerprint

    Dive into the research topics of 'Convex-hull algorithms: Implementation, testing, and experimentation'. Together they form a unique fingerprint.

    Cite this