Experience Report: Growing and Shrinking Polygons for Random Testing of Computational Geometry Algorithms

Advanced search
Browse by:

Department | Year

UCL Theses | Latest

Deposit your research

Experience Report: Growing and Shrinking Polygons for Random Testing of Computational Geometry Algorithms

Sergey, I; (2016) Experience Report: Growing and Shrinking Polygons for Random Testing of Computational Geometry Algorithms. In: ICFP 2016 Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming. (pp. pp. 193-199). ACM Green open access

[thumbnail of Sergey_polygons-draft.pdf]

Preview

Text
Sergey_polygons-draft.pdf - Accepted Version
Download (567kB) | Preview

Abstract

This paper documents our experience of adapting and using the QuickCheck-style approach for extensive randomised property-based testing of computational geometry algorithms. The need in rigorous evaluation of computational geometry procedures has naturally arisen in our quest of organising a medium-size programming contest for second year university students—an experiment we conducted as an attempt to introduce them to computational geometry. The main effort in organising the event was implementation of a solid infrastructure for testing and ranking solutions. For this, we employed functional programming techniques. The choice of the language and the paradigm made it possible for us to engineer, from scratch and in a very short period of time, a series of robust geometric primitives and algorithms, as well as implement a scalable framework for their randomised testing. We describe the main insights, enabling efficient random testing of geometric procedures, and report on our experience of using the testing framework, which helped us to detect and fix a number of issues not just in our programming artefacts, but also in the published algorithms we had implemented.

Type:	Proceedings paper
Title:	Experience Report: Growing and Shrinking Polygons for Random Testing of Computational Geometry Algorithms
Event:	21st ACM SIGPLAN International Conference on Functional Programming (ICFP)
Location:	Nara, JAPAN
Dates:	18 September 2016 - 24 September 2016
ISBN-13:	978-1-4503-4219-3
Open access status:	An open access version is available from UCL Discovery
DOI:	10.1145/2951913.2951927
Publisher version:	https://doi.org/10.1145/2951913.2951927
Language:	English
Additional information:	This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords:	Science & Technology, Technology, Computer Science, Software Engineering, Computer Science, QuickCheck, random testing, computational geometry, visibility, Art Gallery Problem, Scala
UCL classification:	UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
URI:	https://discovery.ucl.ac.uk/id/eprint/1545542