Name
Title | ||
|---|---|---|
An Exact and Optimal Local Solution to the Two-Dimensional Convex Hull of Arbitrary Points Problem. |
Abstract | ||
|---|---|---|
A solution 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(root 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. |
Year | Venue | Keywords |
|---|---|---|
2009 | JOURNAL OF CELLULAR AUTOMATA | Cellular automata,convex hull,two dimensions,grid,non-adjacent points,optimal |
Field | DocType | Volume |
Orthogonal convex hull,Discrete mathematics,Convex conjugate,Combinatorics,Convex combination,Convex hull,Krein–Milman theorem,Convex set,Convex polytope,Convex analysis,Mathematics | Journal | 4 |
Issue | ISSN | Citations |
2 | 1557-5969 | 4 |
PageRank | References | Authors |
0.69 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sami Torbey | 1 | 17 | 3.36 |
| Selim G. Akl | 2 | 2074 | 299.32 |