An Improved Cellular Automata Based Algorithm for the 45-Convex Hull Problem
Adam G. Clarridge and Kai Salomaa
We give a cellular automaton algorithm for solving a version of the convex hull problem. The algorithm is based on the one presented by Torbey and Akl, which requires a global transition rule change in order to complete its operation. By introducing several new states and giving a simpler set of transition rules, we lift the requirement for a global rule change in between the previous algorithm’s shrinking and expanding stages. The algorithm uses several communication states to explicitly detect when the first (shrinking) stage has ended, and relying only on local state information the cellular automaton is able to begin the next (expanding) stage of the computation in such a way that correctness is ensured.
Keywords: Cellular automata, convex hull, 45-convex hull, algorithm.