Ohad Shamir, Sivan Sabato, et al.
Theoretical Computer Science
We observe a somewhat surprising result: Given a set S of n points in E2 and a point q∉S, ⊖(n) time is sufficient to determine a point on the convex hull, CH(S), that is nearest to q when q is exterior to CH(S). However, if q lies in the interior of CH(S), then ⊖(n log n) time is both necessary and sufficient to determine such a point. We also observe that ⊖(n) time suffices to determine whether or not the point q lies inside CH(S). © 1989.
Ohad Shamir, Sivan Sabato, et al.
Theoretical Computer Science
Beomseok Nam, Henrique Andrade, et al.
ACM/IEEE SC 2006
Qing Li, Zhigang Deng, et al.
IEEE T-MI
Xinyi Su, Guangyu He, et al.
Dianli Xitong Zidonghua/Automation of Electric Power Systems