Abstract | ||
---|---|---|
A combinatorial algorithm to find a shortest triangular path STP between two points inside a digital object imposed on triangular grid is designed having $$Ofrac{n}{g} log frac{n}{g}$$ time complexity, n being the number of pixels on the contour of the object and g being the grid size. First the inner triangular cover of the given digital object is constructed which maximally inscribes the object. Certain combinatorial rules are formulated based on the properties of triangular grid and are applied whenever necessary to obtain a shortest triangular path, where the path lies entirely in the digital object and moves only along the grid edges. The length of STP and number of monotonicity may be two useful parameters to determine shape complexity of the object. Experimental results show the effectiveness of the algorithm. |
Year | Venue | Field |
---|---|---|
2016 | DGCI | Discrete mathematics,Combinatorics,Shortest path problem,Combinatorial principles,Yen's algorithm,Pixel,Time complexity,Digital geometry,Grid,Mathematics,K shortest path routing |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
5 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Apurba Sarkar | 1 | 4 | 3.81 |
Arindam Biswas | 2 | 141 | 35.89 |
Shouvick Mondal | 3 | 0 | 0.34 |
Mousumi Dutt | 4 | 25 | 8.54 |