有距离限制的组合几何问题

摘要

平面上给定n个点,其两两之间的距离必定存在最大的与最小的。这两个距离在处理数字竞赛中一类有距离限制的组合几何问题时具有独特的作用。本文旨在介绍处理这类问题所涉及的基本知识和解题思路的分析,寻求解题技巧。我们叫平面上给定的n个点的全体为平面点集,记作G。任两点间的最大距离为G的直径,记为d。对于平面点集G,显然有如下事实: 如G的直径是d,则存在A∈G,B∈G,