货郎担问题的几何解法

摘要

本文提出货郎担问题的一种新的求解方法，即几何解法，它的时间复杂性为：求距离运算次数为Ｏ（ｎｍ），比较次数为Ｏ（ｍａｘ（ｎｍ，ｎｌｏｇｎ），求夹角次数为Ｏ（ｎ＾２／ｍ），其中ｎ为点集中点的数目，ｍ为点集的凸包顶点数。