An efficient incremental algorithm for generating the characteristic shape of a dynamic set of points in the plane. Issue 3 (4th March 2017)

• Record Type: Journal Article
• Authors: Zhong, Xu; Duckham, Matt
• Is Part Of: International journal of geographical information science. Volume 31:Issue 3(2017)
• Page Start: 569
• Page End: 590
• Publication Date: 2017-03-04
• Subjects: Incremental algorithm -- pattern recognition -- footprint -- non-convex -- χ-shape; Geography -- Data processing -- Periodicals; Information storage and retrieval systems -- Periodicals; Géomatique -- Périodiques; Systèmes d'information -- Périodiques; 910.285
• DOI: 10.1080/13658816.2016.1216995
• Languages: English
• ISSNs: 1365-8816

Abstract

ABSTRACT: Several algorithms have been proposed to generate a polygonal 'footprint' to characterize the shape of a set of points in the plane. One widely used type of footprint is the χ -shape. Based on the Delaunay triangulation (DT), χ -shapes guaranteed to be simple (Jordan) polygons. This paper presents for the first time an incremental χ -shape algorithm, capable of processing point data streams. Our incremental χ -shape algorithm allows both insertion and deletion operations, and can handle streaming individual points and multiple point sets. The experimental results demonstrated that the incremental algorithm is significantly more efficient than the existing, batch χ -shape algorithm for processing a wide variety of point data streams.