An Exact and Optimal Local Solution to the Two-Dimensional Convex Hull of Arbitrary Points Problem
Sami Torbey and Selim G. Akl
Asolution to the convex hull problem can be very difficult to achieve using cellular automata, where the input points cannot directly communicate with each other. Previous solutions have been limited to the case where all input points are adjacent in discrete space (they form one non-convex polygon). In this paper, we propose a cellular automaton capable of solving the two dimensional 45-convex hull problem exactly for a set of arbitrary input points. The proposed automaton finds the desired convex hull in O(√ n) running time (where n is the number of cells in the automaton), which is optimal. It uses three states and one transition rule change during execution.