Convex-Hull Algorithms: Implementation, Testing, and Experimentation

Autor: Jyrki Katajainen, Ask Neve Gamby
Jazyk: angličtina
Rok vydání: 2018
Předmět:
Convex hull
Theoretical computer science
Convex hull algorithms
lcsh:T55.4-60.8
Computer science
Performance
Testing
02 engineering and technology
robustness
01 natural sciences
Computational geometry
lcsh:QA75.5-76.95
Theoretical Computer Science
experimentation
Robustness (computer science)
Hull
0202 electrical engineering
electronic engineering
information engineering
computational geometry
lcsh:Industrial engineering. Management engineering
0101 mathematics
Robustness
algorithm engineering
implementation
Implementation
Algorithm engineering
Experimentation
Numerical Analysis
Multiset
algorithm
Quickhull
Rectilinear convex hull
testing
Algorithm
010101 applied mathematics
Computational Mathematics
Computational Theory and Mathematics
rectilinear convex hull
020201 artificial intelligence & image processing
lcsh:Electronic computers. Computer science
convex hull
performance
Zdroj: Algorithms, Vol 11, Iss 12, p 195 (2018)
Gamby, A N & Katajainen, J 2018, ' Convex-hull algorithms : Implementation, testing, and experimentation ', Algorithms, vol. 11, no. 12, 195 . https://doi.org/10.3390/a11120195
Gamby, A N & Katajainen, J 2018, ' Convex-hull algorithms : Implementation, testing, and experimentation ', Algorithms, vol. 11, no. 12, 195, pp. 1-27 . https://doi.org/10.3390/a11120195
Algorithms
Volume 11
Issue 12
ISSN: 1999-4893
DOI: 10.3390/a11120195
Popis: 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&mdash
in the integer-arithmetic setting&mdash
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.
Databáze: OpenAIRE
Externí odkaz:
Nepřihlášeným uživatelům se plný text nezobrazuje