An Improved Implementation and Inalysis of the Diaz and O'Rourke Algorithm for Finding the Simpson Point of a Convex Polygon

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Joyendu Bhadury, Professor, Information Systems and Supply Chain Management (Creator)
Institution
The University of North Carolina at Greensboro (UNCG )
Web Site: http://library.uncg.edu/

Abstract: This paper focuses on the well-known Diaz and O'Rourke [M. Diaz and J. O'Rourke, Algorithms for computing the center of area of a convex polygon, Visual Comput. 10 (1994), 432–442.] iterative search algorithm to find the Simpson Point of a market, described by a convex polygon. In their paper, they observed that their algorithm did not appear to converge pointwise, and therefore, modified it to do so. We first present an enhancement of their algorithm that improves its time complexity from O(log2?) to O(n log 1/?). This is then followed by a proof of pointwise convergence and derivation of explicit bounds on convergence rates of our algorithm. It is also shown that with an appropriate interpretation, our convergence results extend to all similar iterative search algorithms to find the Simpson Point – a class that includes the original unmodified Diaz–O'Rourke algorithm. Finally, we explore how our algorithm and its convergence guarantees might be modified to find the Simpson Point when the demand distribution is non-uniform.

Additional Information

Publication
International Journal of Computer Mathematics, 87(2), 244-259
Language: English
Date: 2010
Keywords
competitive location, geometric optimisation, Simpson Point, centre of area, iterative algorithms

Email this document to