Blumenstein, M 2008, 'Cursive character segmentation using neural network techniques', Studies in Computational Intelligence, vol. 90, pp. 259-275.
View/Download from: Publisher's site
View description>>
The segmentation of cursive and mixed scripts persists to be a difficult problem in the area of handwriting recognition. This research details advances for segmenting characters in off-line cursive script. Specifically, a heuristic algorithm and a neural network-based technique, which uses a structural feature vector representation, are proposed and combined for identifying incorrect segmentation points. Following the location of appropriate anchorage points, a character extraction technique, using segmentation paths, is employed to complete the segmentation process. Results are presented for neural-based heuristic segmentation, segmentation point validation, character recognition, segmentation path detection and overall segmentation accuracy. © 2008 Springer-Verlag Berlin Heidelberg.
Blumenstein, M, Green, S, Fogelman, S, Nguyen, A & Muthukkumarasamy, V 2008, 'Performance analysis of GAME: A generic automated marking environment', Computers and Education, vol. 50, no. 4, pp. 1203-1216.
View/Download from: Publisher's site
View description>>
This paper describes the Generic Automated Marking Environment (GAME) and provides a detailed analysis of its performance in assessing student programming projects and exercises. GAME has been designed to automatically assess programming assignments written in a variety of languages based on the "structure" of the source code and the correctness of the program's output. Currently, the system is able to mark programs written in Java, C++ and the C language. To use the system, instructors are required to provide a simple "marking schema" for each given assessment item, which includes pertinent information such as the location of files and the model solution. In this research, GAME has been tested on a number of student programming exercises and assignments and its performance has been compared against that of a human marker. An in-depth statistical analysis of the comparison is presented, providing encouraging results and directions for employing GAME as a tool for teaching and learning. © 2006 Elsevier Ltd. All rights reserved.
Cha, D, Blumenstein, M, Zhang, H & Jeng, DS 2008, 'A neural-genetic technique for coastal engineering: Determining wave-induced seabed liquefaction depth', Studies in Computational Intelligence, vol. 82, pp. 337-351.
View/Download from: Publisher's site
View description>>
In the past decade, computational intelligence (CI) techniques have been widely adopted in various fields such as business, science and engineering, as well as information technology. Specifically, hybrid techniques using artificial neural networks (ANNs) and genetic algorithms (GAs) are becoming an important alternative for solving problems in the field of engineering in comparison to traditional solutions, which ordinarily use complicated mathematical theories. The wave-induced seabed liquefaction problem is one of the most critical issues for analysing and designing marine structures such as caissons, oil platforms and harbours. In the past, various investigations into wave-induced seabed liquefaction have been carried out including numerical models, analytical solutions and some laboratory experiments. However, most previous numerical studies are based on solving complicated partial differential equations. In this study, the proposed neural-genetic model is applied to wave-induced liquefaction, which provides a better prediction of liquefaction potential. The neural-genetic simulation results illustrate the applicability of the hybrid technique for the accurate prediction of wave-induced liquefaction depth, which can also provide coastal engineers with alternative tools to analyse the stability of marine sediments. © 2008 Springer-Verlag Berlin Heidelberg.
Chen, J & Ying, M 2008, 'Ancilla-Assisted Discrimination Of Quantum Gates', Quantum Information and Computation, vol. 10, no. 1-Feb, pp. 160-177.
View/Download from: UTS OPUS
View description>>
The intrinsic idea of superdense coding is to find as many gates as possible such that they can be perfectly discriminated. In this paper, we consider a basic scheme of discrimination of quantum gates, called ancilla-assisted discrimination, in which a s
Chen, JF, Duan, R, Ji, Z, Ying, M & Yu, JX 2008, 'Existence Of Universal Entangler', Journal of Mathematical Physics, vol. 49, no. 1, pp. 1-7.
View/Download from: UTS OPUS or Publisher's site
View description>>
A gate is called an entangler if it transforms some (pure) product states to entangled states. A universal entangler is a gate which transforms all product states to entangled states. In practice, a universal entangler is a very powerful device for gener
Chitambar, E, Duan, R & Shi, Y 2008, 'Tripartite entanglement transformations and tensor rank', Physical Review Letters, vol. 101, no. 14.
View/Download from: Publisher's site
View description>>
A basic question regarding quantum entangled states is whether one can be probabilistically converted to another through local operations and classical communication exclusively. While the answer for bipartite systems is known, we show that for tripartite systems, this question encodes some of the most challenging open problems in mathematics and computer science. In particular, we show that there is no easy general criterion to determine the feasibility, and in fact, the problem is NP hard. In addition, we find obtaining the most efficient algorithm for matrix multiplication to be precisely equivalent to determining the maximum rate to convert the Greenberger-Horne-Zeilinger state to a triangular distribution of three EPR states. Our results are based on connections between multipartite entanglement and tensor rank (also called Schmidt rank), a key concept in algebraic complexity theory. © 2008 The American Physical Society.
Chitambar, EA, Duan, R & Shi, Y 2008, 'Tripartite Entanglement Transformations And Tensor Rank', Physical Review Letters, vol. 101, no. 14, pp. 1-4.
View/Download from: UTS OPUS or Publisher's site
View description>>
A basic question regarding quantum entangled states is whether one can be probabilistically converted to another through local operations and classical communication exclusively. While the answer for bipartite systems is known, we show that for tripartit
de Burgh, MD, Langford, NK, Doherty, AC & Gilchrist, A 2008, 'Choice of measurement sets in qubit tomography', PHYSICAL REVIEW A, vol. 78, no. 5.
View/Download from: Publisher's site
Duan, R & Shi, Y 2008, 'Entanglement Between Two Uses Of A Noisy Multipartite Quantum Channel Enables Perfect Transmission Of Classical Information', Physical Review Letters, vol. 101, no. 2, pp. 1-4.
View/Download from: UTS OPUS or Publisher's site
View description>>
Suppose that m senders want to transmit classical information to n receivers with zero probability of error using a noisy multipartite communication channel. The senders are allowed to exchange classical, but not quantum, messages among themselves, and t
Duan, R, Feng, Y & Ying, M 2008, 'Local Distinguishability Of Multipartite Unitary Operations', Physical Review Letters, vol. 100, no. 2, pp. 1-4.
View/Download from: UTS OPUS or Publisher's site
View description>>
We show that any two different unitary operations acting on an arbitrary multipartite quantum system can be perfectly distinguished by local operations and classical communication when a finite number of runs is allowed. Intuitively, this result indicate
Duan, R, Feng, Y & Ying, M 2008, 'Local distinguishability of multipartite unitary operations.', Physical review letters, vol. 100, no. 2, p. 020503.
View/Download from: Publisher's site
View description>>
We show that any two different unitary operations acting on an arbitrary multipartite quantum system can be perfectly distinguished by local operations and classical communication when a finite number of runs is allowed. Intuitively, this result indicates that the lost identity of a nonlocal unitary operation can be recovered locally. No entanglement between distant parties is required.
Dur, W, Bremner, MJ & Briegel, HJ 2008, 'Quantum simulation of interacting high-dimensional systems: The influence of noise', Physical Review A, vol. 78, no. 5, p. 052325.
View/Download from: UTS OPUS or Publisher's site
View description>>
We consider the simulation of interacting high-dimensional systems using pairwise interacting qubits. The main tool in this context is the generation of effective many-body interactions, and we examine a number of different protocols for obtaining them. These methods include the usage of higher-order processes commutator method , unitary conjugation or graph state encoding, as well as teleportation-based approaches. We illustrate and compare these methods in detail and analyze the time cost for simulation. In the second part of the paper, we investigate the influence of noise on the simulation process. We concentrate on errors in the interaction Hamiltonians and consider two generic noise models: i timing errors in pairwise interactions and ii noisy pairwise interactions described by Master equations of Lindblad form. We analyze and compare the effect of noise for the different simulation methods and propose a way to significantly reduce the influence of noise by making use of entanglement purification together with a teleportation-based protocol.
Ferrie, C & Emerson, J 2008, 'Frame representations of quantum mechanics and the necessity of negativity in quasi-probability representations', JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL, vol. 41, no. 35.
View/Download from: Publisher's site
Gao, X, Lu, R, Ouyang, D, Sun, J, Li, S, Shi, C, Yao, T, Lu, R, Han, Z, Wang, J & Cao, C 2008, 'AI In China: A Survey', IEEE Intelligent Systems, vol. 23, no. 6, pp. 26-32.
View/Download from: UTS OPUS or Publisher's site
View description>>
This article consists of nine short essays discussing research pursued by AI researchers in China and their perspectives on research in several AI subareas. The article first introduces the mechanization of mathematics, an area in which Chinese scientists have made significant contributions. It then discusses research in automated reasoning, temporal and spatial knowledge representation and reasoning, natural language understanding, intelligent diagnosis, multiagent systems, computational intelligence, large-scale knowledge processing, and several research streams integrating AI techniques with methods from other fields. Finally, the article makes suggestions concerning future AI research in China.
Gauger, EM, Rohde, PP, Stoneham, AM & Lovett, BW 2008, 'Strategies for entangling remote spins with unequal coupling to an optically active mediator', NEW JOURNAL OF PHYSICS, vol. 10.
View/Download from: UTS OPUS or Publisher's site
Haselgrove, HL & Rohde, PP 2008, 'Trade-off between the tolerance of located and unlocated errors in nondegenerate quantum error-correcting codes', Quantum Information and Computation, vol. 8, no. 5, pp. 0399-0410.
View description>>
In a recent study [Rohde et al., quant-ph/0603130 (2006)] of several quantum error correcting protocols designed for tolerance against qubit loss, it was shown that these protocols have the undesirable effect of magnifying the effects of depolarization noise. This raises the question of which general properties of quantum error-correcting codes might explain such an apparent trade-off between tolerance to located and unlocated error types. We extend the counting argument behind the well-known quantum Hamming bound to derive a bound on the weights of combinations of located and unlocated errors which are correctable by nondegenerate quantum codes. Numerical results show that the bound gives an excellent prediction to which combinations of unlocated and located errors can be corrected with high probability by certain large degenerate codes. The numerical results are explained partly by showing that the generalized bound, like the original, is closely connected to the information-theoretic quantity the quantum coherent information. However, we also show that as a measure of the exact performance of quantum codes, our generalized Hamming bound is provably far from tight. © Rinton Press.
Haselgrove, HL & Rohde, PP 2008, 'Trade-off between the tolerance of located and unlocated errors in nondegenerate quantum error-correcting codes', QUANTUM INFORMATION & COMPUTATION, vol. 8, no. 5, pp. 399-410.
Hsieh, M, Devetak, I & Winter, A 2008, 'Entanglement-Assisted Capacity of Quantum Multiple-Access Channels', IEEE Transactions On Information Theory, vol. 54, no. 7, pp. 3078-3090.
View/Download from: UTS OPUS or Publisher's site
View description>>
We find a regularized formula for the entanglement-assisted (EA) capacity region for quantum multiple access channels (QMAC). We illustrate the capacity region calculation with the example of the collective phase-flip channel which admits a single-letter characterization. On the way, we provide a first-principles proof of the EA coding theorem based on a packing argument. We observe that the Holevo-Schumacher-Westmoreland theorem may be obtained from a modification of our EA protocol. We remark on the existence of a family hierarchy of protocols for multiparty scenarios with a single receiver, in analogy to the two-party case. In this way, we relate several previous results regarding QMACs.
Ji, Z, Wang, G, Duan, R, Feng, Y & Ying, M 2008, 'Parameter Estimation of Quantum Channels', IEEE Transactions On Information Theory, vol. 54, no. 11, pp. 5172-5185.
View/Download from: UTS OPUS or Publisher's site
View description>>
The efficiency of parameter estimation of quantum channels is studied in this paper. We introduce the concept of programmable parameters to the theory of estimation. It is found that programmable parameters obey the standard quantum limit strictly; hence, no speedup is possible in its estimation. We also construct a class of nonunitary quantum channels whose parameter can be estimated in a way that the standard quantum limit is broken. The study of estimation of general quantum channels also enables an investigation of the effect of noises on quantum estimation.
Kremsky, I, Hsieh, M-H & Brun, TA 2008, 'Classical enhancement of quantum-error-correcting codes', PHYSICAL REVIEW A, vol. 78, no. 1.
View/Download from: Publisher's site
Lanyon, BP, Weinhold, TJ, Langford, NK, O'Brien, JL, Resch, KJ, Gilchrist, A & White, AG 2008, 'Manipulating biphotonic qutrits', PHYSICAL REVIEW LETTERS, vol. 100, no. 6.
View/Download from: Publisher's site
Lee, J, Sanmugarasa, K, Blumenstein, M & Loo, YC 2008, 'Improving the reliability of a Bridge Management System (BMS) using an ANN-based Backward Prediction Model (BPM)', Automation in Construction, vol. 17, no. 6, pp. 758-772.
View/Download from: Publisher's site
View description>>
The slow adoption of Bridge Management Systems (BMSs) and its impractical future prediction of the condition rating of bridges are attributed to the inconsistency between BMS inputs and bridge agencies' existing data for a BMS in terms of compatibility and the enormous number of bridge datasets that include historical structural information. Among these, historical bridge element condition ratings are some of the key pieces of information required for bridge asset prioritisation but in most cases only limited data is available. This study addresses the abovementioned difficulties faced by bridge management agencies by using limited historical bridge inspection records to model time-series element-level data. This paper presents an Artificial Neural Network (ANN) based prediction model, called the Backward Prediction Model (BPM), for generating historical bridge condition ratings using limited bridge inspection records. The BPM employs historical non-bridge datasets such as traffic volumes, populations and climates, to establish correlations with existing bridge condition ratings from very limited bridge inspection records. The resulting model predicts the missing historical condition ratings of individual bridge elements. The outcome of this study can contribute to reducing the uncertainty in predicting future bridge condition ratings and so improve the reliability of various BMS analysis outcomes. © 2008 Elsevier B.V. All rights reserved.
Li, S & Ying, M 2008, 'Soft constraint abstraction based on semiring homomorphism', Theoretical Computer Science, vol. 403, no. 2-3, pp. 192-201.
View/Download from: UTS OPUS or Publisher's site
View description>>
The semiring-based constraint satisfaction problems (semiring CSPs), proposed by Bistarelli, Montanari and Rossi [S. Bistarelli, U. Montanari, F. Rossi, Semiring-based constraints solving and optimization, Journal of the ACM 44 (2) (1997) 201236], is a very general framework of soft constraints. In this paper we propose an abstraction scheme for soft constraints that uses semiring homomorphism. To find optimal solutions of the concrete problem, we first work in the abstract problem and find its optimal solutions, and then use them to solve the concrete problem. In particular, we show that a mapping preserves optimal solutions if and only if it is an order-reflecting semiring homomorphism. Moreover, for a semiring homomorphism ? and a problem P over S, if t is optimal in ?(P), then there is an optimal solution View the MathML source of P such that View the MathML source has the same value as t in ?(P).
Rohde, K & Rohde, PP 2008, 'HOW TO MEASURE ECOLOGICAL HOST SPECIFICITY', VIE ET MILIEU-LIFE AND ENVIRONMENT, vol. 58, no. 2, pp. 121-124.
Rohde, PP, Munro, WJ, Ralph, TC, Van Loock, P & Nemoto, K 2008, 'Practical effects in the preparation of cluster states using weak non-linearities', Quantum Information and Computation, vol. 8, no. 1-2, pp. 0053-0067.
View/Download from: UTS OPUS
View description>>
We discuss experimental effects in the implementation of a recent scheme for performing bus mediated entangling operations between qubits. Here a bus mode, a strong coherent state, successively undergoes weak Kerr-type non-linear interactions with qubits. A quadrature measurement on the bus then projects the qubits into an entangled state. This approach has the benefit that entangling gates are non-destructive, may be performed non-locally, and there is no need for efficient single photon detection. In this paper we examine practical issues affecting its experimental implementation. In particular, we analyze the effects of post-selection errors, qubit loss, bus loss, mismatched coupling rates and mode-mismatch. We derive error models for these effects and relate them to realistic fault-tolerant thresholds, providing insight into realistic experimental requirements. © Rinton Press.
Rohde, PP, Munro, WJ, Ralph, TC, van Loock, P & Nemoto, K 2008, 'Practical effects in the preparation of cluster states using weak non-linearities', QUANTUM INFORMATION & COMPUTATION, vol. 8, no. 1-2, pp. 53-67.
Schirmer, SG, Oi, DKL & Devitt, SJ 2008, 'Physics-based mathematical models for quantum devices via experimental system identification', PHYSICS-BASED MATHEMATICAL MODELS FOR LOW-DIMENSIONAL SEMICONDUCTOR NANOSTRUCTURES: ANALYSIS AND COMPUTATION, vol. 107.
View/Download from: Publisher's site
Stephens, AM, Evans, ZWE, Devitt, SJ & Hollenberg, LCL 2008, 'Asymmetric quantum error correction via code conversion', PHYSICAL REVIEW A, vol. 77, no. 6.
View/Download from: Publisher's site
Stephens, AM, Evans, ZWE, Devitt, SJ, Greentree, AD, Fowler, AG, Munro, WJ, O'Brien, JL, Nemoto, K & Hollenberg, LCL 2008, 'Deterministic optical quantum computer using photonic modules', PHYSICAL REVIEW A, vol. 78, no. 3.
View/Download from: Publisher's site
Wang, G & Ying, M 2008, 'Deterministic Distributed Dense Coding With Stabilizer States', Physical Review A, vol. 77, no. 3, pp. 1-10.
View/Download from: UTS OPUS or Publisher's site
View description>>
We consider the possibility of using stabilizer states to perform deterministic dense coding among multiple senders and a single receiver. In the model we studied, the utilized stabilizer state is partitioned into several subsystems and then each subsyst
Wang, G & Ying, M 2008, 'Perfect Many-To-One Teleportation With Stabilizer States', Physical Review A, vol. 77, no. 3, pp. 1-12.
View/Download from: UTS OPUS or Publisher's site
View description>>
We study the possibility of performing perfect teleportation of unknown quantum states from multiple senders to a single receiver with a previously shared stabilizer state. In the model we considered, the utilized stabilizer state is partitioned into sev
Witzigmann, B, Tomamichel, M, Steiger, S, Veprek, RG, Kojima, K & Schwarz, UT 2008, 'Analysis of gain and luminescence in violet and blue GaInN-GaN quantum wells', IEEE JOURNAL OF QUANTUM ELECTRONICS, vol. 44, no. 1-2, pp. 144-149.
View/Download from: Publisher's site
Wu, X & Duan, R 2008, 'Exact Quantum Search By Parallel Unitary Discrimination Schemes', Physical Review A, vol. 78, no. 1, pp. 1-8.
View/Download from: UTS OPUS or Publisher's site
View description>>
We study the unsorted database search problem with items N from the viewpoint of unitary discrimination. Instead of considering the famous O(root N) Grover bounded-error algorithm for the original problem, we seek the results for the exact algorithms, i.
Xin, Y & Duan, R 2008, 'Local Distinguishability Of Orthogonal 2 Circle Times 3 Pure States', Physical Review A, vol. 77, no. 1, pp. 1-10.
View/Download from: UTS OPUS
View description>>
We present a complete characterization for the local distinguishability of orthogonal 2 circle times 3 pure states except for some special cases of three states. Interestingly, we find there is a large class of four or three states that are indistinguish
Greentree, AD, Jong, LM, Van Donkelaar, JA, Devitt, SJ & Cole, JH 2008, 'Spatial adiabatic passage as a quantum wire', 2008 INTERNATIONAL CONFERENCE ON NANOSCIENCE AND NANOTECHNOLOGY, International Conference on Nanoscience and Nanotechnology, IEEE, Melbourne, AUSTRALIA, pp. 156-159.
View/Download from: Publisher's site
Hsieh, M, Luo, Z & Brun, T 2008, 'Secret keys assisted private classical communication capacity over quantum channels', The 8th Asian Conference on Quantum Information Science (AQIS08), Seoul, Korea.
View description>>
We prove a regularized formula for the secret key-assisted capacity region of a quantum channel for transmitting private classical information. This result parallels the work of Devetak on entanglement assisted quantum communication capacity \cite{DHW05RI}. This formula provides a new family protocol, the private father protocol, under the resource inequality framework that includes private classical communication \it{without} secret key assistance as a child protocol.
Lanyon, BP, Weinhold, TJ, Langford, NK, Barbieri, M, De Almeida, MP, Gilchrist, A, James, DFV & White, AG 2008, 'Photonic quantum computing: shor's algorithm and the road to fault-tolerance', Conference on Quantum Electronics and Laser Science (QELS) - Technical Digest Series.
View/Download from: Publisher's site
Li, J, Kowalski, T, Renz, J & Li, S 2008, 'Combining binary constraint networks in qualitative reasoning', Proceeding of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence: Frontiers in Artificial Intelligence and Applications, European Conference on Artificial Intelligence, IOS Press, Patras, Greece, pp. 515-519.
View/Download from: UTS OPUS
View description>>
Constraint networks in qualitative spatial and temporal reasoning are always complete graphs. When one adds an extra element to a given network, previously unknown constraints are derived by intersections and compositions of other constraints, and this may introduce inconsistency to the overall network. Likewise, when combining two consistent networks that share a common part, the combined network may become inconsistent. In this paper, we analyse the problem of combining these binary constraint networks and develop certain conditions to ensure combining two networks will never introduce an inconsistency for a given spatial or temporal calculus. This enables us to maintain a consistent world-view while acquiring new information in relation with some part of it. In addition, our results enable us to prove other important properties of qualitative spatial and temporal calculi in areas such as representability and complexity.
Qiao, Y & Tartary, C 2008, 'Counting Method for Multi-party Computation over Non-abelian Groups', LNCS - Cryptology and Network Security - Proceedings of the 7th International Conference, Cryptology and Network Security, Springer, Hong Kong, pp. 162-177.
View/Download from: UTS OPUS or Publisher's site
View description>>
In the Crypto'07 paper [5], Desmedt et al. studied the problem of achieving secure n-party computation over non-Abelian groups. The function to be computed is f G (x 1,...,x n ) :?=?x 1 ·...·x n where each participant P i holds an input x i from the non-commutative group G. The settings of their study are the passive adversary model, information-theoretic security and black-box group operations over G. They presented three results. The first one is that honest majority is needed to ensure security when computing f G . Second, when the number of adversary t=?n2?-1, they reduced building such a secure protocol to a graph coloring problem and they showed that there exists a deterministic secure protocol computing f G using exponential communication complexity. Finally, Desmedt et al. turned to analyze random coloring of a graph to show the existence of a probabilistic protocol with polynomial complexity when t?
Schirmer, SG, Kandasamy, G & Devitt, SJ 2008, 'Control paradigms for quantum engineering', 2008 3RD INTERNATIONAL SYMPOSIUM ON COMMUNICATIONS, CONTROL AND SIGNAL PROCESSING, VOLS 1-3, 3rd IEEE International Symposium on Control, Communications and Signal Processing (ISCCSP 2008), IEEE, St Julians, MALTA, pp. 966-+.
View/Download from: Publisher's site
Thornton, J, Faichney, J, Blumenstein, M & Hine, T 2008, 'Character recognition using hierarchical vector quantization and temporal pooling', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp. 562-572.
View/Download from: Publisher's site
View description>>
In recent years, there has been a cross-fertilization of ideas between computational neuroscience models of the operation of the neocortex and artificial intelligence models of machine learning. Much of this work has focussed on the mammalian visual cortex, treating it as a hierarchically- structured pattern recognition machine that exploits statistical regularities in retinal input. It has further been proposed that the neocortex represents sensory information probabilistically, using some form of Bayesian inference to disambiguate noisy data. In the current paper, we focus on a particular model of the neocortex developed by Hawkins, known as hierarchical temporal memory (HTM). Our aim is to evaluate an important and recently implemented aspect of this model, namely its ability to represent temporal sequences of input within a hierarchically structured vector quantization algorithm. We test this temporal pooling feature of HTM on a benchmark of cursive handwriting recognition problems and compare it to a current state-of-the-art support vector machine implementation. We also examine whether two pre-processing techniques can enhance the temporal pooling algorithm's performance. Our results show that a relatively simple temporal pooling approach can produce recognition rates that approach the current state-of-the-art without the need for extensive tuning of parameters. We also show that temporal pooling performance is surprisingly unaffected by the use of preprocessing techniques. © 2008 Springer Berlin Heidelberg.
Zhang, X, Liu, W, Li, S & Ying, M 2008, 'Reasoning with Cardinal Directions: An Efficient Algorithm', Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence vol 1, National Conference of the American Association for Artificial Intelligence, AAAI Press, Chicago, Illinois, USA, pp. 387-392.
View/Download from: UTS OPUS
View description>>
Direction relations between extended spatial objects are important commonsense knowledge. Recently, Goyal and Egenhofer proposed a formal model, called Cardinal Direction Calculus (CDC), for representing direction relations between connected plane regions. CDC is perhaps the most expressive qualitative calculus for directional information, and has attracted increasing interest from areas such as artificial intelligence, geographical information science, and image retrieval. Given a network of CDC constraints, the consistency problem is deciding if the network is realizable by connected regions in the real plane. This paper provides a cubic algorithm for checking consistency of basic CDC constraint networks. As one byproduct, we also show that any consistent network of CDC constraints has a canonical realization in digital plane. The cubic algorithm can also been adapted to cope with disconnected regions, in which case the current best algorithm is of time complexity O(n5).