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.
An Improved Implementation and Inalysis of the Diaz and O'Rourke Algorithm for Finding the Simpson Point of a Convex Polygon
PDF (Portable Document Format)
378 KB
Created on 7/11/2014
Views: 970
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