Experience Report: Growing and Shrinking Polygons for Random Testing of Computational Geometry Algorithms
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.
I am a lecturer (assistant professor) at University College London.
Prior to joining UCL, I was a postdoctoral researcher at IMDEA Software Institute (Madrid, Spain). I defended my PhD in 2012 in the DistriNet research group at the Department of Computer Sciences of KU Leuven (Belgium). Before that I received my MSc degree in Mathematics and Computer Science from Saint Petersburg State University (Russia) in 2008.
My research interests dwell in the area of the design and implementation of programming languages, including but not limited to program semantics, certified programming, concurrency and abstract interpretation. I am particularly interested in developing verification techniques and static analyses for higher-order and concurrent programs.
Tue 20 SepDisplayed time zone: Osaka, Sapporo, Tokyo change
10:35 - 12:15 | |||
10:35 25mTalk | A Glimpse of Hopjs Research Papers DOI | ||
11:00 25mTalk | Experience Report: Growing and Shrinking Polygons for Random Testing of Computational Geometry Algorithms Research Papers Ilya Sergey University College London, UK DOI | ||
11:25 25mTalk | Think Like a Vertex, Behave Like a Function! A Functional DSL for Vertex-Centric Big Graph Processing Research Papers Kento Emoto Kyushu Institute of Technology, Japan, Kiminori Matsuzaki Kochi University of Technology, Japan, Zhenjiang Hu National Institute of Informatics, Japan, Akimasa Morihata University of Tokyo, Japan, Hideya Iwasaki University of Electro-Communications, Japan DOI | ||
11:50 25mTalk | Datafun: A Functional Datalog Research Papers DOI | ||
