| Аннотация | Рассматривается задача об открытии мэрией города фиксированного числа n культурных центров. Целью мэрии является эффективное разделение города на n областей Di , при условии, что для каждой области Di культурный центр открывается в геометрической медиане ( ) m Di . Анализируется ситуация, в которой жители расселены равномерно с плотностью ρ = 1. Если все жители согласны с предписаниями мэрии и каждый житель области Di с адре- сом x посещает центр ( ) m Di , его выигрыш равен λ − / area( ) ( , ( )) ii i D dxmD , где area( ) Di — площадь области Di , численно совпадающая с ее населением, λi — фиксированные положительные веса (полезности). Показано, что мэрия всегда может разбить город на заданное число областей так, чтобы жителям наиболее выгодно было посещение центра своей области. Такое разбиение называется равновесным. Оказывается, что в нем совместные границы двух соседних областей являются кусками гипербол. Для нахождения равновесного разбиения используется техника потенциалов. А именно: на множестве всех разбиений длины n вводится функционал, который как раз достигает своего минимума на равновесном разбиении. Доказательство существования минимума достаточно сложно и проводится путем сведения непрерывной задачи к дискретному случаю. Непрерывная область разбиения заменяется дискретным подмножеством решетки, а непрерывный функционал — функционалом, определенным на раз- биениях дискретного множества. Обратная редукция осуществляется путем пре- дельного перехода при ε → 0. Подробно рассмотрены свойства геометрических медиан конечных подмножеств ε S , содержащихся в единичном круге. Особое внимание уделено массивным множествам ε S , т.е. множествам, для которых ε > ε2 S A / . |
|---|