An improved implementation and analysis of the Diaz and O'Rourke algorithm for finding the Simpson point of a convex polygon

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(log²ϵ) 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.

Keywords:

• competitive location
• geometric optimisation
• Simpson Point
• centre of area
• iterative algorithms

2000 AMS Subject Classification :

• 51-XX
• 68-XX
• 68WXX
• 90BXX
• 90-08