Graph-based Study on Consistency Checking for Point Objects

摘要：

In this paper.we address the problem of consistency checking for Point Objects.A coordinate graph representation is introduced. The basic idea is to project the spatial constraints on both X and Y dimensions .and the graph is constructed on each dimension.By using the graph representation,the problem of consistency checking is then transformed to a graph cycle detection problem. The consistency checking can be achieved with O(N+E) time as well as space complexin,where N is the number of spatial objects.and E is number of spatial predicates in the constraint. The proposed approach to consistency- checking for point objects is faster than O(N2) when the number of predicates is much smaller than N2 . The algorithm can also guarantee the global consistency.

关键词： spatial constraint consistency checking graph

作者: Liu Zheng-lin Gao Ai-hua Zhao Yong-gang Guan Jian Wei Rui

作者单位: Information Technology Department, E&A College, Hebei Normal University of Science & Technology Qinhuangdao, China

会议类型: 国际会议

会议名称: 2011 3rd International Conference on Computer Engineering and Applications(2011第三届计算机工程与应用国际会议 ICCEA2011)

会议地点: 海口

会议语种:英文

页码: 444-446

在线出版日期: 2011-07-15（万方平台首次上网日期，不代表论文的发表时间）