Optimal Algorithms for Circle Partitioning
Optimal Algorithms for Circle Partitioning
复制标题
圆划分的最优算法
DOI：
10.1007/bfb0045097
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
Da
中科院分区：
文献类型：
--
作者：
K. Tsai;Da
给定一组n点f和一个整数k，我们希望找到一个尺寸的k子集，以便这些点在圆上“均匀分布”。偶数。 mod k）和UI如果最小（u）是所有尺寸k子集或最大值（u）中最大的，则u均匀分布。位置问题。
Given a set of n points F on a circle and an integer k, we would like to find a size k subset of F such that these points are “evenly distributed” on the circle. We define two different criteria to capture the intuitive notion of evenness. Let U be a set of points on a circle and let u1, u2, u3,..., uk be the order of the points in U visited clockwise starting from u1. Denote by d; the distance between ui-1(mod k) and ui. Let min(U) = min(di) denote the minimum distance between every pair of adjacent points and similarly max(U) = max(di) denote the maximum distance between every pair of adjacent points. We feel that a set U is evenly distributed if min(U) is the largest among all the size k subset or max(U) is the smallest among all the size k subset. We call the former problem maxmin point location problem and the latter minmax point location problem.