An efficient incremental algorithm for generating the characteristic shape of a dynamic set of points in the plane

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.

KEYWORDS:

• Incremental algorithm
• pattern recognition
• footprint
• non-convex
• χ-shape

Disclosure statement

No potential conflict of interest was reported by the authors.

Algorithm 1 -shape algorithm with preparation for future insertion or deletion

Algorithm 2 Incremental -shape algorithm (insertion)

Algorithm 3 Incremental -shape algorithm (deletion)

Additional information

Funding

This work was supported by the Australian Research Council: [Grant Number LP120200584].