几何:计算几何,计算所有朋友点

Question

给定n个点,其中没有三个是共线的.i和j,如果用i&j作为直径形成的圆不包含任何其他点,则2分是朋友.在O(nlogn)中给出所有这些点

Answer 1

您正在尝试计算文献中所谓的相对邻域图.由两点确定的lune必须为空.关于这个主题有很多文献.你可以从维基百科的文章开始.正如用户tmyklebu所说,它是Delaunay三角测量的一个子集.

      

更正.我误解了这些条件,正如阿西里亲切地解释的那样.相关的图形是Gabriel图,它也有相当多的文献: