Pareto-Optimality of Cognitively Preferred Polygonal Hulls for Dot Patterns

Antony Galton

In Christian Freksa, Nora S. Newcombe, Peter Gärdenfors, and Stefan Wölfl (editors), Spatial Cognition VI: Learning, Reasoning, and Talking about Space, Proceedings of International Conference Spatial Cognition 2008, Freiburg, Germany, September 15-19, 2008, Springer, pages 409-425
ISBN 3-542-87600-6

Abstract

In several areas of research one encounters the problem of generating an outline that is in some way representative of the spatial distribution of a pattern of dots. Several different algorithms have been published which can generate such outlines, but the detailed evaluation of such algorithms has mostly concentrated on their computational and mathematical properties, while the adequacy of the resulting outlines themselves has been left as a matter of informal human judgment. In this paper it is proposed to investigate the perceptual acceptability of outlines independently of any particular algorithm for generating them, in order to determine objective criteria for evaluating outlines from the full range of possibilities in a way that is conformable to human intuitive assessments. For the sake of definiteness it is assumed that the outline to be produced is a simple closed polygon whose vertices are elements of the given dot pattern, all remaining elements of the dot pattern being in the interior of the polygon. It is hypothesised that to produce a cognitively acceptable outline one should seek simultaneously to minimise both the area and perimeter of the polygon, and that therefore the points in area-perimeter space corresponding to cognitively optimal outlines will lie on or close to the Pareto front. A small pilot study was conducted, the results of which lend strong support to the hypothesis. The paper concludes with some suggestions for further more detailed investigations.

This paper was awarded the BEST PAPER AWARD at Spatial Cognition 2008.

On-line version
Preprint
Slides from the conference presentation


Antony Galton
Last modified: Mon Mar 29 13:06:20 BST 2010