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