Ubiquitous Computing and Communication Journal
Disseminator of Knowledge
Home Home | About Us About Us | Contact Us Contact Us | Login Tuesday, February 25, 2020
Title: Education and out of the box thinking – linearization of Graham’s scan algorithm complexity as fruit of education policy
Authors: Mr. Veljko Petrovic, Dr. Dragan Ivetic
The question of educational policy is considered with reference to its effect on student creativity. An example of this effect is presented – the linearization of Graham’s scan algorithm. The linearzation is described in detail with reference to how varying aspects of it originate with the original educational environment.The Graham’s Scan approach to two-dimensional convex hull calculation is considered. The performance bottleneck is found in the sorting step that precedes the Graham’s Scan scanning operation. Methods are considered to eliminate this bottleneck. The method chosen is replacing the O(n lg n) sorting algorithm normally used with a radix sort. To operate within Graham’s scan, the radix sort algorithm must be modified. The main modification is getting it to operate on real numbers. This is achieved by using the fact that digital computers only operate on a countable and finite subset of real numbers, and using this fact to reduce the problem of sorting by real number to sorting by integer. The ramifications of this modification are taken into consideration in the light of previous theoretical work in this area. Performance as compared to other algorithms is considered. Further, the consequences of a proof that the lower bound for the temporal complexity of two-dimensional convex hull algorithms is O(n lg n) are considered.