Предположим, что у меня есть полный, неориентированный граф G с расстоянием, связанным с каждым ребром. Значение ребра (u, v), имеющего длину l, является "точками u и v не может быть ближе друг к другу, чем l". Моя цель состоит в том, чтобы заложить узлы этого графика в плоскости, чтобы ни одна из этих ограничений расстояния не была нарушена и чтобы выпуклая оболочка точек имела наименьшую общую площадь. В качестве примера предположим, что у меня есть куча электрических компонентов, которые я хочу поместить на чип, каждый из которых генерирует некоторое количество электрических помех. Если я поставил компоненты слишком близко друг к другу, они начнут мешать друг другу, делая всю систему бесполезной. Учитывая минимальные расстояния, каждая точка должна быть от точки друг друга, какой наиболее экономичный способ размещения компонентов на чипе?
Я понятия не имею, как начать думать об этом. Я также не знаю, как проблема может быть обобщена на более высокомерный случай (точки упаковки в гиперплоскость). Кто-нибудь знает о хорошем способе решения этой проблемы?