摘要: The map construction problem (MCP) is defined as a spatial data integration relating to the of region into data. Although purely geometric regions known and efficient, algorithms preserving thematic are much more difficult. A naive approach MCP runs in O((nmlg nm)2 + k) time for m composed with n line segments on average k segment intersections. newO((n+k)(lg n+m+lgm2)) algorithm presented solve MCP. has been implemented experiments show that it significantly faster than approach.
sci-hub.se 参考文章(9)
Martin Erwig, Markus Schneider, Formalization of Advanced Map Operations ,(2000)
Mark McKenney, Region Extraction and Verification for Spatial and Spatio-temporal Databases statistical and scientific database management. pp. 598- 607 ,(2009) , 10.1007/978-3-642-02279-1_42
Mark McKenney, Markus Schneider, Topological relationships between map geometries database systems for advanced applications. pp. 110- 125 ,(2008) , 10.1007/978-3-540-78568-2_11
Bentley, Ottmann, Algorithms for Reporting and Counting Geometric Intersections IEEE Transactions on Computers. ,vol. 28, pp. 643- 647 ,(1979) , 10.1109/TC.1979.1675432
Markus Schneider, Thomas Behr, Topological relationships between complex spatial objects ACM Transactions on Database Systems. ,vol. 31, pp. 39- 81 ,(2006) , 10.1145/1132863.1132865
Rene De La Briandais, File searching using variable length keys Papers presented at the the March 3-5, 1959, western joint computer conference on XX - IRE-AIEE-ACM '59 (Western). pp. 295- 298 ,(1959) , 10.1145/1457838.1457895
Michel Scholl, Agnès Voisard, Thematic Map Modeling Lecture Notes in Computer Science. ,vol. 409, pp. 167- 190 ,(1989) , 10.1007/3-540-52208-5_27
Markus Schneider, Mark Mckenney, Map algebra: a data model and implementation of spatial partitions for use in spatial databases and geographic information systems University of Florida. ,(2008)
Edward Fredkin, Trie memory Communications of The ACM. ,vol. 3, pp. 490- 499 ,(1960) , 10.1145/367390.367400