Qualitative Spatial Representation and Reasoning: An Overview
Fundamenta InformaticaePublished 20 January 2001
Anthony G. Cohn, Shyamanta M. Hazarika
Citations675
SJR quartileQ3
SJR score0.29
SNIP0.62
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The paper is a overview of the major qualitative spatial representation and reasoning techniques including ontological aspects, topology, distance, orientation and shape, and qualitative spatial reasoning including reasoning about spatial change.
Abstract
The paper is a overview of the major qualitative spatial representation and reasoning techniques. We survey the main aspects of the representation of qualitative knowledge including ontological aspects, topology, distance, orientation and shape. We also consider qualitative spatial reasoning including reasoning about spatial change. Finally there is a discussion of theoretical results and a glimpse of future work. The paper is a revised and condensed version of [33,34].
Keywords
Computer ScienceSocial Sciences
Communications of the ACMMaintaining knowledge about temporal intervals
7,550 Citations1983James F. Allen
An interval-based temporal logic is introduced, together with a computationally effective reasoning algorithm based on constraint propagation, which is notable in offering a delicate balance between space and time.
Psychological ReviewRecognition-by-components: A theory of human image understanding.
5,507 Citations1987Irving Biederman
Recognition-by-components (RBC) provides a principled account of the heretofore undecided relation between the classic principles of perceptual organization and pattern recognition.
Proceedings of the Royal Society of London. Series B, Biological sciencesRepresentation and recognition of the spatial organization of three-dimensional shapes
2,183 Citations1978David Marr, H. K. Nishihara
The human visual process can be studied by examining the computational problems associated with deriving useful information from retinal images by applying the approach to the problem of representing three-dimensional shapes for the purpose of recognition.
Artificial IntelligenceQualitative process theory
2,023 Citations1984Kenneth D. Forbus
This paper describes the basic concepts of qualitative process theory, several different kinds of reasoning that can be performed with them, and discusses its implications for causal reasoning.
International Journal of Geographical Information SystemsPoint-set topological spatial relations
1,651 Citations1991Max J. Egenhofer, Robert Franzosa
A novel theory of topological spatial relations between sets is developed in which the relations are defined in terms of the intersections of the boundaries and interiors of two sets, and it is shown that these relations correspond to some of the standard set theoretical andTopological spatial Relations between sets such as equality, disjointness and containment in the interior.
Parts : a Study in Ontology
983 Citations1987Peter Simons
Robotics and Autonomous SystemsA robot exploration and mapping strategy based on a semantic hierarchy of spatial representations
707 Citations1991Benjamin Kuipers, Yung-Tai Byun
A robust qualitative method is developed that can build an accurate map of a previously unkown environment in spite of substantial random and systematic sensorimotor error and successful navigation is not critically dependent on the accuracy, or even the existence, of the geometrical description.
Artificial IntelligenceTemporal reasoning based on semi-intervals
670 Citations1992Christian Freksa
A generalization of Allen's interval-based approach to temporal reasoning is presented, with the notion of ‘conceptual neighborhood’ of qualitative relations between events is central and knowledge about relations between events can be represented much more compactly.
GeoInformaticaQualitative Spatial Representation and Reasoning with the Region Connection Calculus
566 Citations1997Anthony G. Cohn, Brandon Bennett +2 more
This paper surveys the work of the qualitative spatial reasoning group at the University of Leeds and motivates the use of regions as the primary spatial entity and shows how a rich language can be built up from surprisingly few primitives.
IEEE Computer Graphics and ApplicationsSolid Modeling: A Historical Summary and Contemporary Assessment
519 Citations1982Requicha, Voelcker
A new generation of industrial geometry systems is emerging based on the technology of the 1970's, which will require more research in the generations of the eighties and nineties.
Lecture notes in computer scienceA small set of formal topological relationships suitable for end-user interaction
503 Citations1993Eliseo Clementini, Paolino Di Felice +1 more
The first method is an extension of the geometric point-set approach by taking the dimension of the intersections into account, which results in a very large number of different topological relationships for point, line, and area features.
Elsevier eBooksRepresentations of Commonsense Knowledge
454 Citations1990
The power of representations in expressing world knowledge and in supporting significant inferences is analyzed using many detailed examples and the book is an essential reference for AI researchers and developers.
Artificial IntelligenceUncertainty measures of rough set prediction
418 Citations1998Ivo Düntsch, Günther Gediga
This work presents three model selection criteria, using information theoretic entropy in the spirit of the minimum description length principle, based on the principle of indifference combined with the maximum entropy principle, thus keeping external model assumptions to a minimum.
Journal of Visual Languages & ComputingQualitative spatial reasoning about distances and directions in geographic space
417 Citations1992Andrew U. Frank
A method for formal, qualitative reasoning about distances and cardinal directions in geographic space, using an algebraic approach to define two operations, composition and inverse, and completes the completion of distance or direction symbols with an identity element.
Journal of the ACMReasoning about temporal relations
407 Citations1995Bernhard Nebel, Hans-Jürgen Bürckert
Using an extensive machine-generated case analysis, it is shown that the ORD-Horn subclass is a maximal tractable subclass of the full algebra (assuming P ≠ NP).
Notre Dame Journal of Formal LogicA calculus of individuals based on ``connection''.
394 Citations1981Bowman L. Clarke
Calcul des individus, dans la ligne de la mereologie de Lesniewski et de ses developpements philosophiques chez Whitehead et Goodman, comprend trois parties: une partie mereologique (systematisation des predicats mereologiques), partie quasi booleenne (introduction des operateurs booleens and de l'individu universel).
Lecture notes in computer scienceQualitative Representation of Spatial Knowledge
349 Citations1994Daniel Hernández
This work presents a cognitive perspective on knowledge representation from a qualitative perspective and extends the basic model to include qualitative representations of positions in 2-D.
Lecture notes in computer scienceA formal definition of binary topological relationships
337 Citations1989Max J. Egenhofer
A formal definition of spatial relationships is necessary to clarify the users' diverse understanding of spatial relationship and to actually deduce relationships among spatial objects.
Lecture notes in computer scienceReasoning about gradual changes of topological relationships
336 Citations1992Max J. Egenhofer, Khaled K. Al-Taha
This model describes a partial order over topological relationships and provides a measure to assess how far two relationships are apart from each other and provides answers to three kinds of qualitative space-time inferences.
Artificial IntelligenceA theory of abstraction
336 Citations1992Fausto Giunchiglia, Toby Walsh
This paper proposes the beginnings of a theory of reasoning with abstraction which captures and generalizes most previous work in the area and provides the foundations for the mechanization of abstraction inside an abstract proof checker.
Artificial IntelligenceQualitative representation of positional information
305 Citations1997Eliseo Clementini, Paolino Di Felice +1 more
The model presented in this paper has potential applications in areas as diverse as Geographical Information Systems (GIS), Computer Aided Design (CAD), and Document Recognition.
Journal of Visual Languages & ComputingReasoning about Cardinal Directions
296 Citations1998Gérard Ligozat
This paper is about the complexity of reasoning about cardinal directions in 2D space and considers the problem of picture description as presented by Chang and Jungert [2].
Journal of Visual Languages & ComputingQuery Processing in Spatial-Query-by-Sketch
284 Citations1997Max J. Egenhofer
The representation of a sketch is described and the design of the constraint relaxation methods used during query processing are outlined.
Data & Knowledge EngineeringParts, wholes, and part-whole relations: The prospects of mereotopology
249 Citations1996Achille C. Varzi
Computers & GraphicsModelling topological spatial relations: Strategies for query processing
247 Citations1994Eliseo Clementini, Jayant Sharma +1 more
This paper investigates the processing of spatial queries with topological constraints, for which current database solutions are inappropriate and presents algorithms for minimizing these computations.
International Journal of Geographical Information SystemsOn the equivalence of topological relations
231 Citations1995Max J. Egenhofer, Robert Franzosa
This paper refines the model of empty/non-empty 4-intersections with further topological invariants to account for more details about topological relations.
Artificial IntelligenceA process-grammar for shape
223 Citations1988Michael Leyton
It is argued that the inference of history arises from a newly discovered duality between curvature extrema and symmetry structure, and a formal grammar is developed by which someone can infer the processes that produced the second stage from the first.
The Philosophical ReviewHoles and Other Superficialities.
205 Citations1996David Lewis, Roberto Casati +1 more
IEEE Transactions on ComputersMeasuring Concavity on a Rectangular Mosaic
198 Citations1972Jack Sklansky
A theory for describing and measuring the concavities of cellular complexes (digitized silhouettes) is developed that involves the use of the minimum-perimeter polygon and its convex hull.
Lecture notes in computer scienceQualitative spatial representation and reasoning techniques
183 Citations1997Anthony G. Cohn
The state of the art in Qualitative Spatial Reasoning is surveyed, covering representation and reasoning issues as well as pointing to some application areas.
National Conference on Artificial IntelligenceA qualitative model for space
177 Citations1990Amitabha Mukerjee, Gene Joe
This work describes a systematic representation that builds spatial maps based on local qualitative relations between objects that is free of subjective bias, and is complete in the qualitative sense of distinguishing all overlap/ tangency/nocontact geometries.
Toward a geometry of common sense: a semantics and a complete axiomatization of mereotopology
170 Citations1995Nicholas Asher, Laure Vieu
This work offers an alternative to Tarski, starting with mereotopological notions that have proved useful in the semantic analysis of spatial expressions and gives a complete axiomatization of this account of mereotipological reasoning.
International Journal of Approximate ReasoningApproximate topological relations
168 Citations1997Eliseo Clementini, Paolino Di Felice
In this paper, approximate topological relations are destined to capture boundary uncertainty, variations over time, proximity measures, and vector-raster representations.
Information Sciences - ApplicationsA comparison of methods for representing topological relationships
167 Citations1995Eliseo Clementini, Paolino Di Felice
It is shown that the calculus-based method is able to distinguish among finer topological configurations than most of the point-set methods.
Principles of Knowledge Representation and ReasoningSpatial Reasoning with Propositional Logics
163 Citations1994Brandon Bennett
By encoding spatial relationships in a propositional representation automated reasoning becomes more effective, and specifies representations in both classical and intuitionistic propositional logic, which provide for efficient reasoning about a large class of spatial relations.
Representing and Reasoning with Qualitative Spatial Relations About Regions
151 Citations1997Anthony G. Cohn, Brandon Bennett +2 more
Qualitative Reasoning (QR) has now become a mature subfield of AI as its tenth annual international workshop, several books, and a wealth of conference and journal publications testify.
Computers & Chemical EngineeringFormal order-of-magnitude reasoning in process engineering
145 Citations1988Michael L. Mavrovouniotis, George Stephanopoulos
O(M) relations permit order-of-magnitude analysis in process engineering, suitable for many process engineering activities, such as preliminary design of process flowsheets, planning of process operations, design of control structures for chemical plants, fault simulation and diagnosis, process trend analysis and analysis of biochemical pathways.
Modelling topological and metrical properties in physical processes
141 Citations1989David Randell, Anthony G. Cohn
The power of the formalism is illustrated by modelling the process of phagocytosis of theamoeba, together with an outline of how many pro-perties of physical entities and relations can be modelled within a unitary framework.
Similarity of Spatial Scenes
138 Citations1998H. Tom Bruns, Max J. Egenhofer
This paper describes a computational method to formally assess the similarity of spatial scenes based on the ordering of spatial relations and shows that two scenes that require a large number of changes are less similar than Scenes that require fewer changes.
Lecture notes in computer scienceReasoning about ordering
136 Citations1995Christoph Schlieder
A system of line segment relations which generalizes Allen's system of interval relations to two dimensions is introduced and it is shown that this generalization differs in interesting properties from the generalizations based on topological relations which have been proposed so far.
Computer Vision Graphics and Image ProcessingCodon constraints on closed 2D shapes
133 Citations1985Whitman Richards, Donald D. Hoffman
For smooth closed strings that represent the bounding contour (silhouette) of many smooth 3D objects, the constraints are so strong that sequences containing 6 elements yield only 33 generic shapes as compared with a possible number of 15,625 combinations.
Logic Journal of IGPLModal Logics for Qualitative Spatial Reasoning
131 Citations1996Brandon Bennett
It is shown how 0-order logics can be given a spatial interpretation: constants denote regions and logical operators correspond to operations on regions which are important for characterising spatial situations.
BIROn (Birkbeck, University of London)Spatio-temporal representation and reasoning based on RCC-8
131 Citations2000Frank Wolter, Michael Zakharyaschev
Elsevier eBooksCriteria for Representations of Shape
125 Citations1983Michael Brady
A representation for the shape of surfaces is proposed, called Curvature Patches, used to extend Smoothed Local Symmetries to a novel three-dimensional representation.
A pointless theory of space based on strong connection and congruence
125 Citations1996Stefano Borgo, Nicola Guarino +1 more
A logical theory of space where only tridimensional regions are assumed in the domain is presented, and three distinct primitives are used to describe their mereological, topological and morphological properties.
The MonistA Connection Based Approach to Common-sense Topological Description and Reasoning
117 Citations1996Nicholas M. Gotts, J. M. Gooday +1 more
Lecture notes in computer scienceThe Mereotopology of Discrete Space
117 Citations1999Antony Galton
An attempt is made to bridge the gap between the continuous and discrete models of space by developing a high-level qualitative spatial theory premissed on a discrete model of space, exploiting the intrinsic metric of the discrete framework to define a measure of distinctness for regions, which affords an analogue of continuous change.
MPG.PuRe (Max Planck Society)Preferred mental models in qualitative spatial reasoning: A cognitive assessment of Allen's calculus
115 Citations1995Markus Knauff, Reinhold Rauh +1 more
Algorithms and combinatoricsAllowable Sequences and Order Types in Discrete and Computational Geometry
112 Citations1993Jacob E. Goodman, Richard Pollack
The allowable sequence associated to a configuration of points was first developed by the authors in order to investigate what combinatorial structure lay behind the Erdős-Szekeres conjecture, and an object emerged that had considerable intrinsic interest and turned out to be effective in the solution of several other classical problems.
A Qualitative Theory of Motion Based on Spatio-Temporal Primitives.
111 Citations1998Philippe Müller
It is shown what kind of properties usually assumed as desirable parts of any space-time theory are recovered from the authors' model, thus giving a sound theoretical basis for a natural, qualitative representation of motion.
Lecture notes in computer scienceA cognitive assessment of topological spatial relations: Results from an empirical investigation
105 Citations1997Markus Knauff, Reinhold Rauh +1 more
In the reported empirical investigation, subjects had to group numerous spatial configurations consisting of two circles with respect to their similarity and support the assumption that both theories are cognitively adequate in a number of important aspects.
Lecture notes in computer scienceComputing transitivity tables: A challenge for automated theorem provers
104 Citations1992David Randell, Anthony G. Cohn +1 more
Any automated theorem prover which can effectively generate the entries for such transitivity tables would mark significant progress in automated theorem proving.
Theoretical Computer ScienceA relation – algebraic approach to the region connection calculus
104 Citations2001Ivo Düntsch, Hui Wang +1 more
It is proved that a refined version of the RCC5 table has as models all atomless Boolean algebras B with the natural ordering as the “part-of” relation, and that the table is closed under first-order definable relations iff B is homogeneous.
Maximal Tractable Fragments of the Region Connection Calculus: A Complete Analysis
102 Citations1999Jochen Renz
A general method for proving tractability of reasoning over disjunctions of jointly exhaustive and pairwise disjoint relations of Allen's temporal interval relations and their spatial counterpart, the R.CC8 relations by Randell, Cui, and Colin is presented.
Qualitative simulation based on a logical formalism of space and time
101 Citations1992Zhanfeng Cui, Anthony G. Cohn +1 more
An envisionment-based qualitative simulation program that implements part of an axiomatic, first order theory that has been developed to represent and reason about space and time.
Elsevier eBooksQualitative Kinematics: A framework
99 Citations1990Kenneth D. Forbus, Paul E. Nielsen +1 more
It is proposed that no general-purpose, purely qualitative kinematics exists, and the MD/PV model of spatial reasoning is proposed, which combines the power of diagrams with qualitative representations and connectivity as the organizing principle for kinematic state.
On the utilization of spatial structures for cognitively plausible and efficient reasoning
96 Citations2003Christian Freksa, Karsten Zimmermann
The authors present an approach to representing and processing qualitative orientation information which is motivated by cognitive considerations about the knowledge acquisition process and a basic iconic notation for spatial orientation relations which exploits the spatial structure of the domain.
Image and Vision ComputingConstructing qualitative event models automatically from video input
90 Citations2000Jonathan H. Fernyhough, Anthony G. Cohn +1 more
An implemented technique for generating event models automatically based on qualitative reasoning and a statistical analysis of video input is described, which learns various event models expressed in the qualitative calculus which represent human observable events.
Lecture notes in computer scienceEvaluating and refining computational models of spatial relations through cross-linguistic human-subjects testing
89 Citations1995David Mark, David Comas +4 more
Human-subjects testing based on a sound formal model is outlined as an effective way to evaluate and refine computational models of spatial relations.
A three-level approach to the semantics of space
88 Citations1993Michel Aurnague, Laure Vieu
To analyze the semantics of some of these expressions, this work systematically looks for valid reasoning schemata involving them and enables the testing of the proposed formal system as well as the evaluation of the definitions obtained for the studied lexemes.
Lecture notes in computer scienceProximity operators for qualitative spatial reasoning
85 Citations1995Mark Gahegan
This paper discusses how a model to support proximal reasoning could be constructed, with the meaning of linguistic variables being instantiated within a given context at execution time.
Psychology Press eBooksQualitative Reasoning About Space and Motion
83 Citations2014Kenneth D. Forbus
The grammar inhuman factors design of an interactive graphics system and the psychology of how novices learn computer programming are studied.
Lecture notes in computer scienceTopological relations between regions in ρ2 and ℤ2
79 Citations1993Max J. Egenhofer, Jayant Sharma
The 9-intersection is applied, a frequently used formalism for topological spatial relations between objects represented in a vector data model, and it is found that the set of all possible topological relations between regions in ρ2 is a subset of the topological Relations that can be realized between two bounded, extended objects in ℤ2.
Lecture notes in computer scienceTowards a qualitative theory of movement
79 Citations1995Antony Galton
By attending closely to the constraints imposed by continuity on the temporal behaviour of different fluents the authors develop theory of dominance, which enables us to generate ab initio the perturbation relation on the full set of positional relations.
The EGG/YOLK reliability hierarchy
77 Citations1994Fritz Lėhmann, Anthony G. Cohn
This work exploits Cui, Cohn and Randell's Qualitative Spatial Simulation program to create the hierarchy of all possible relations between source and target EGG/YOLK types, ranked by reliability.
Artificial IntelligenceDefault reasoning about spatial occupancy
75 Citations1995Murray Shanahan
Algorithms which generate behavioral models for mechanical devices by first using kinematic analysis to find state variables and then using dynamics to find differential equations relating the state variables are presented.
Foundations of spatioterminological reasoning with description logics
72 Citations1998Volker Haarslev, Carsten Lutz +1 more
This paper presents a method for reasoning about spatial objects and their qualitative spatial relationships that integrates quantitative and qualitative information with terminological reasoning, and presents the description logic ALCRP(D) and an appropriate concrete domain D for polygons.
Artificial IntelligenceA symbolic approach to qualitative kinematics
71 Citations1992Boi Faltings
This paper shows how a qualitative kinematic analysis can be based solely on symbolic reasoning and evaluation of predicates on metric dimensions, which allows symbolic reasoning about kinematics without explicit numerical representations of object dimensions, and automatic generation of operators relating kinematically goals to shape modifications which may achieve them.
Journal of Artificial Intelligence ResearchA Complete Classification of Tractability in RCC-5
70 Citations1997Thomas Drakengren, Peter Jönsson
This work investigates the computational properties of the spatial algebra RCC-5 which is a restricted version of the RCC framework for spatial reasoning and identifies all maximal tractable subalgebras which are four in total.
Philosophical StudiesThe structure of spatial localization
70 Citations1996Roberto Casati, Achille C. Varzi
Lecture notes in computer scienceA canonical model for a class of areal spatial objects
68 Citations1993Michael Worboys, Petros Bofakos
This study aims to model an appropriate set of 2-dimensional spatial objects embedded in R2 with the usual metric and topology and aims to capture explicitly some important topological properties of the spatial objects, e.g. connectedness and region inclusion.
Oncology nursing forumBoundaries: An essay in mereotopology
68 Citations1997Barry Smith
The author thanks Carola Eschenbach, Nicola Guarino, Christopher Habel, Wolfgang Heydrich, Barbara Morawska, Mark Textor, Achille Varzi, Graham White and Wojciech Zelaniec for helpful comments.
Journal of Philosophical LogicA Complete Axiom System for Polygonal Mereotopology of the Real Plane
66 Citations1998Ian Pratt‐Hartmann, Dominik Schoop
A calculus for mereotopological reasoning in which two-dimensional spatial regions are treated as primitive entities in which polygonal open subsets of the real plane serve as elements of the domain is presented.
International Journal of Human-Computer StudiesClassical mereology and restricted domains
66 Citations1995Carola Eschenbach, Wolfgang Heydrich
It is claimed that the structural differences between restricted domains are not based on different mereological concepts, but on different concepts of being a whole, which sheds more light on the specific nature of these domains, their similarities and differences.
International Joint Conference on Artificial IntelligenceTowards an Integrated Logic of Space, Time and Motion.
58 Citations1993Antony Galton
This paper shows how Allen’s temporal logic, with the modifications suggested by Galton to enable it to accommodate continuityphenomena, can be combined with the spatial logic of Randall, Cui and Cohn to yield a useful framework for reasoning about the motion of a rigid body in space.
Medical Entomology and ZoologyQualitative spatial reasoning : theory and practice ; application to robot navigation
55 Citations1998M. Teresa Escrig
This work provides an approach for integrating the qualitative concepts of orientation, distance, and cardinal directions, using points as well as extended objects as primitive of reasoning, based on Constraint Logic Programming.
Artificial IntelligenceResponse to my critics
55 Citations1996Hubert L. Dreyfus
This paper shows how to modify an R n model so as to have an appropriate topological structure, and illustrates how the new models support standard reasoning algorithms, provide simple models for previously difficult situations, and suggest interesting new analyses based on change or non-change in scene topology.
International Journal of Human-Computer StudiesTaxonomies of logically defined qualitative spatial relations
54 Citations1995Anthony G. Cohn, David Randell +1 more
This paper develops a taxonomy of qualitative spatial relations for pairs of regions, which are all logically defined from two primitive (but axiomatized) notions, which allows many more relations to be defined.
Lecture notes in computer scienceEnhancing qualitative spatial reasoning — Combining orientation and distance
52 Citations1993Kai Zimmermann
A new approach is presented that allows to use and to combine knowledge about distances and positions in a qualitative way based on perceptual and cognitive considerations about the capabilities of humans navigating within their environments.
Lecture notes in computer scienceComputational properties of qualitative spatial reasoning: First results
50 Citations1995Bernhard Nebel
This paper focuses on the so-called RCC approach and uses Bennett's encoding of spatial reasoning in intuitionistic logic in order to show that consistency checking for the topological base relations can be done efficiently and proves path-consistency is sufficient for deciding global consistency.
Principles of Knowledge Representation and ReasoningHow Far Can We ‘C’? Defining a ‘Doughnut’ Using Connection Alone
50 Citations1994Nicholas M. Gotts
The paper shows how taxonomies of topological properties and relations can be developed, using the single primitive C, where C(x, y) indicates that regions x and y are ‘connected’, meaning that their closures share at least one point.
Notre Dame Journal of Formal LogicOntologies for Plane, Polygonal Mereotopology
50 Citations1997Oliver Lemon, Ian Pratt‐Hartmann
It is concluded that useful alternative ontologies of the plane are, if anything, less parsimonious than the one which they are supposed to replace.
Lecture notes in computer scienceThe algebraic structure of sets of regions
49 Citations1997John G. Stell, Mike Worboys
A proof that elements of certain Heyting algebras provide models of the Region-Connection Calculus developed by Cohn et al. is presented, using the mathematically well known techniques of “pointless topology”.
A foundation for region-based qualitative geometry
49 Citations2000Brandon Bennett, Anthony G. Cohn +2 more
A categorical axiom system, whose models can be interpreted classically in terms of Cartesian spaces over ℝ, and it is shown that within this system the concept of sphere and the congruence relation are interdefinable.
Journal of Logic and ComputationModal logics for incidence geometries
48 Citations1997Philippe Balbiani
Computers & Mathematics with ApplicationsExploiting lattices in a theory of space and time
48 Citations1992David Randell, Anthony G. Cohn
An axiomatic theory expressed in a first order predicate logic formalism that modifies and extends Bowman Clarke's calculus of individuals and various classification hierarchies are singled out and expressed as lattice structures.
A canonical model of the region connection calculus
46 Citations1997Jochen Renz
Space, Time, and Movement
44 Citations1997Antony Galton
This chapter is intended to contribute to the intense interest in laying bare and systematising the conceptual schemes underlying the authors' everyday competence in handling such notions as time, space, and movement in disciplines such as philosophy and artificial intelligence.
ConstraintsConstraint Networks of Topological Relations and Convexity
43 Citations1999Ernest Davis, Nicholas M. Gotts +1 more
This paper considers constraint networks whose nodes are regular regions and whose constraints have the following forms: the eight “base relations” of [12], which describe binary topological relations of containment and adjacency between regions; and shows an important expressivity result for this language.
Postgraduate Medical JournalSemantique des relations spatiales et inferences spatio-temporelles : une contribution a l'etude des structures formelles de l'espace en langage naturel
43 Citations1991Laure Vieu
Artificial IntelligenceA method of spatial reasoning based on qualitative trigonometry
41 Citations1998Jiming Liu
This paper illustrates how the QTRIG relationships can be employed in generating qualitative spatial descriptions in two-dimensional Euclidean geometric problems, and furthermore, how the derived qualitative spatial describe can be used to guide a simulated-annealing-based exact quantitative value assignment.
Lecture notes in computer scienceAtomicity vs. Infinite Divisibility of Space
39 Citations1999Claudio Masolo, Laure Vieu
This paper investigates the possibility of characterizing properties of space such as divisibility, density and atomicity in spaces modeled by mereologies and mereotopologies, and properties of atoms like extension and self-connectedness will be considered.
Connection Relations in Mereotopology
32 Citations1998Anthony G. Cohn, Achille C. Varzi
A model-theoretic framework forigating and comparing a variety of mereotopological theories with respect to the intended interpretation of their primitives and the composition of their intended do- mains is provided.
Describing Rigid Body Motions in a Qualitative Theory of Spatial Regions
32 Citations2000Brandon Bennett, Anthony G. Cohn +2 more
The expressive power of a recently developed qualitative region-based geometry is explored and applied to the problem of representing and reasoning about the motion of rigid bodies within a confining environment.
A Mereological Approach to Representing Spatial Vagueness
30 Citations1994Anthony G. Cohn
This paper develops a relation of Crisping (reducingimprecision or vagueness) between pair of pair sofvague'spatial regions: those with indeterminateboundaries.
Lecture notes in computer scienceThe voronoi model and cultural space: applications to the social sciences and humanities
27 Citations1993Geoffrey Edwards
It is shown that the Voronoi model favors a rich qualitative database of the kind which will be found in culturally intensive application domains and is also a closer fit to qualitative data representation and analysis than other models.
…