Abstract
The planar Euclidean version of the traveling salesperson problem requires finding the shortest tour through a two-dimensional array of points. MacGregor and Ormerod (1996) have suggested that people solve such problems by using a global-to-local perceptual organizing process based on the convex hull of the array. We review evidence for and against this idea, before considering an alternative, local-to-global perceptual process, based on the rapid automatic identification of nearest neighbors. We compare these approaches in an experiment in which the effects of number of convex hull points and number of potential intersections on solution performance are measured. Performance worsened with more points on the convex hull and with fewer potential intersections. A measure of response uncertainty was unaffected by the number of convex hull points but increased with fewer potential intersections. We discuss a possible interpretation of these results in terms of a hierarchical solution process based on linking nearest neighbor clusters.
Article PDF
Similar content being viewed by others
References
Attneave, F. (1974). Apparent movement and the what-where connection.Psychologia,17, 108–120.
Caelli, T. M. (1981). Some psychophysical determinants of discrete Moiré patterns.Biological Cybernetics,39, 97–103.
Carlin, B. P., &Louis, T. A. (2000).Bayes and empirical Bayes methods for data analysis (2nd ed.). New York: Chapman & Hall.
Chater, N., &Vitányi, P. (2003). Simplicity: A unifying principle in cognitive science?Trends in Cognitive Sciences,7, 19–22.
Chi, M. T. H., Glaser, R., &Farr, M. J. (1988).The nature of expertise. Hillsdale, NJ: Erlbaum.
Cohen, J. (1994). The earth is round (p<.05).American Psychologist,49, 997–1003.
Dawson, M. R. W. (1991). The how and why of what went where in apparent motion: Modeling solutions to the motion correspondence problem.Psychological Review,98, 569–603.
Duncan, C. P. (1959). Recent research on human problem solving.Psychological Bulletin,56, 397–429.
Edwards, W., Lindman, H., &Savage, L. J. (1963). Bayesian statistical inference for psychological research.Psychological Review,70, 193–242.
Ericsson, K. A., &Lehmann, A. C. (1996). Expert and exceptional performance: Evidence of maximal adaptation to task constraints.Annual Review of Psychology,47, 273–305.
Flood, M. M. (1956). The travelling salesman problem.Operations Research,4, 61–75.
Gelman, A., Carlin, J. B., Stern, H. S., &Rubin, D. B. (1995).Bayesian data analysis. London: Chapman & Hall.
Gigerenzer, G., &Todd, P. M. (1999).Simple heuristics that make us smart. New York: Oxford University Press.
Glass, L. (1969). Moiré effect from random dots.Nature,243, 578–580.
Golden, B., Bodin, L., Doyle, T., &Stewart, W. (1980). Approximate travelling salesman algorithms.Operations Research,28, 694–711.
Graham, S. M., Joshi, A., &Pizlo, Z. (2000). The traveling salesman problem: A hierarchical model.Memory & Cognition,28, 1191–1204.
Howson, C., &Urbach, P. (1993).Scientific reasoning: The Bayesian approach. La Salle, IL: Open Court.
Hunter, J. E. (1997). Needed: A ban on the significance test.Psychological Science,8, 3–7.
Hwang, F. K., Richards, D. S., &Winter, P. (1992).The Steiner tree problem. Amsterdam: Elsevier.
Johnsonbaugh, R. (2001).Discrete mathematics. Upper Saddle River, NJ: Prentice-Hall.
Kass, R. E., &Raftery, A. E. (1995). Bayes factors.Journal of the American Statistical Association,90, 773–795.
Kolers, P. A. (1972).Aspects of motion perception. London: Pergamon.
Lawler, E. L., Lenstra, J. K., Rinooy Kan, A. H. G., &Schmoys, D. B. (1985).The traveling salesman problem: A guided tour of combinatorial optimization. Chichester, U.K.: Wiley.
Lee, M. D., &Vickers, D. (2000). The importance of the convex hull for human performance on the traveling salesman problem: A comment on MacGregor and Ormerod (1996).Perception & Psychophysics,62, 226–228.
Lee, R. K. L. (1985).A heuristic approach to the traveling salesman problem [Unpublished Management Rep.]. Victoria, BC: University of Victoria, School of Public Administration.
Leonard, T., &Hsu, J. S. J. (1999).Bayesian methods: An analysis for statisticians and interdisciplinary researchers. New York: Cambridge University Press.
Lindley, D. V. (1972).Bayesian statistics: A review. Philadelphia: Society for Industrial and Applied Mathematics.
Lovett, M. C. (2002). Problem solving. In H. Pashler & D. Medin (Eds.),Stevens’ Handbook of experimental psychology: Vol. 2. Memory and cognitive processes (pp. 317–362). New York: Wiley.
MacGregor, J. N., &Ormerod, T. [C.] (1996). Human performance on the traveling salesman problem.Perception & Psychophysics,58, 527–539.
MacGregor, J. N., &Ormerod, T. C. (2000). Evaluating the importance of the convex hull in solving the Euclidean version of the traveling salesperson problem: Reply to Lee and Vickers (2000).Perception & Psychophysics,62, 1501–1503.
MacGregor, J. N., Ormerod, T. C., &Chronicle, E. P. (1999). Spatial and contextual factors in the traveling salesperson problem.Perception,28, 1417–1428.
MacGregor, J. N., Ormerod, T. C., &Chronicle, E. P. (2000). A model of human performance on the traveling salesperson problem.Memory & Cognition,28, 1183–1190.
Motter, B. C., &Belky, E. J. (1998). The zone of focal attention during active visual search.Vision Research,38, 1007–1022.
Navon, D. (1976). Irrelevance of figural identity for resolving ambiguities in apparent motion.Journal of Experimental Psychology: Human Perception & Performance,2, 130–138.
Newell, A., &Simon, H. A. (1972).Human problem solving. Englewood Cliffs, NJ: Prentice-Hall.
O’Rourke, J. (1994).Computational geometry in C. New York: Cambridge University Press.
Palmer, S. E. (1999).Vision science: Photons to phenomenology. Cambridge, MA: MIT Press.
Pomerantz, J. R. (1981). Perceptual organization and information processing. In M. Kubovy & J. R. Pomerantz (Eds.),Perceptual organization (pp. 141–180). Hillsdale, NJ: Erlbaum.
Press, W. H. (1992).Numerical recipes in FORTRAN: The art of scientific computing (2nd ed.). Cambridge: Cambridge University Press.
Quintas, L. V., &Supnick, F. (1965). On some properties of shortest Hamiltonian circuits.American Mathematical Monthly,72, 977–980.
Rainville, S. J. M., &Kingdom, F. A. A. (2002). Scale invariance is driven by stimulus density.Vision Research,42, 351–367.
Reinelt, G. (1994). The traveling salesman: Computational solutions for TSP applications. InLecture notes in computer science (Vol. 840). Berlin: Springer-Verlag.
Resnick, R., &Glaser, L. B. (1976). Problem solving and intelligence. In L. B. Resnick (Ed.),The nature of intelligence (pp. 205–230). Hillsdale, NJ: Erlbaum.
Ross, J., Badcock, D. R., &Hayes, A. (2000). Coherent global motion in the absence of coherent velocity signals.Current Biology,10, 679–682.
Schwarz, G. (1978). Estimating the dimension of a model.Annals of Statistics,6, 461–464.
Shannon, C. E. (1948). The mathematical theory of communication.Bell Systems Technical Journal,27, 379–243, 623–656.
Sivia, D. S. (1996).Data analysis: A Bayesian tutorial. Oxford: Oxford University Press, Clarendon Press.
Sternberg, R. J. (1982). Reasoning, problem solving, and intelligence. In R. J. Sternberg (Ed.),Handbook of intelligence (pp. 225–307). New York: Cambridge University Press.
Ullman, S. (1979).The interpretation of visual motion. Cambridge, MA: MIT Press.
van Rooij, I., Stege, U., &Schactman, A. (2003). Convex hull and tour crossings in the Euclidean traveling salesperson problem: Implications for human performance studies.Memory & Cognition,31, 215–220.
Vickers, D., Bovet, P., Lee, M. D., &Hughes, P. (2003). The perception of minimal structures: Performance on open and closed versions of visually presented Euclidean travelling salesperson problems.Perception,32, 871–886.
Vickers, D., Butavicius, M. A., Lee, M. D., &Medvedev, A. (2001). Human performance on visually presented traveling salesman problems.Psychological Research,65, 34–45.
Vickers, D., Dry, M., Lee, M. D.., & Hughes, P. (2003).The role of nearest neighbours in the perception of Glass patterns. Manuscript submitted for publication.
Vickers, D., Mayo, T., Heitmann, M., Lee, M. D., & Hughes, P. (in press). Intelligence and individual differences in performance on three types of visually presented optimisation problems.Personality & Individual Differences.
Vickers, D., & Preiss, A. K. (2003).Impressions of motion from Glass patterns. Manuscript submitted for publication.
Vickers, D., Preiss, A. K., & Hughes, P. (2003).The role of nearest neighbours in the perception of structure and motion in dot patterns. Manuscript submitted for publication.
Wilf, H. S. (1986).Algorithms and complexity. Englewood Cliffs, NJ: Prentice-Hall.
Author information
Authors and Affiliations
Corresponding author
Additional information
The research reported in this paper was supported by Australian Research Council Grant DP0211150 to D.V. and M.D.L.
Rights and permissions
About this article
Cite this article
Vickers, D., Lee, M.D., Dry, M. et al. The roles of the convex hull and the number of potential intersections in performance on visually presented traveling salesperson problems. Memory & Cognition 31, 1094–1104 (2003). https://doi.org/10.3758/BF03196130
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.3758/BF03196130