Теорвер и точки

[Hamster]

Сразу скажу - ответа не знаю - может, есть простое решение, может, нет.

Берется геометрическая фигура ( скажем, квадрат ). В фигуре равномерно разбрасывается N пылинок.

Две пылинки A и B считаются "соседними", если есть такая точка C, что AC = BC < CD для любой другой пылинки D.

Каково распределение расстояний между соседними пылинками?

[venco]

А определение намеренно несимметрично?
Может так оказаться, что А и В - соседние, а В и А - нет.

[O.K.]

Передумал.

[Hamster]

Исправил, извиняюсь. Все симметрично.

[Hamster]

Иллюстрация



задача найти распределение расстояний между "центрами" граничащих многоугольников. На Википедии не смотреть.

[venco]

По моему, аналитически вычислить это нереально.
Рассмотрите простейший случай - просто распределение расстояния между двумя случайными точками на квадрате. Уже в этом случае распределение нетривиально.
То что это называется диаграммой Вороного (Voronoi diagram) я и без Википедии знал, но решить поставленную задачу это не поможет.

[Hamster]

распределение расстояния между случайными или ближайшими точками?

если между ближайшими, то, без учета краевых эффектов,

p(r) dr = (1-π r^2 / A)^(N-1) (2 π r dr / (A - π r^2)) ~ exp(-N π r^2 / A) (2 π r dr / (A - π r^2))

по идее, в моем случае должно быть аналогичное поведение.

[venco]

распределение расстояния между случайными или ближайшими точками?

Их только две - они же и ближайшие.

без учета краевых эффектов

А эта поблажка откуда взялась?

[Hamster]

распределение расстояния между случайными или ближайшими точками?

Их только две - они же и ближайшие.

Это совсем другая проблема - тут краевые эффекты важны - в моей проблеме точек много и поведением возле края фигуры в пределе N -> infinity можно пренебречь.

[O.K.]

Передумал.

[voyager]

Лет 8 назад мне пришлось решать аналитически "простую" задачу. Так вот, решается она довольно тупо:
PDF(ro) = CDF(ro)' . CDF(ro) = Pr(ro < R), ro = (x2-x1)^2 + (y1-y2)^2
Потом рассматриваются различние возможности для R, неравенства решаются графически и т.п. Можно и сразу решить, если правильно Якобиан посчитать (х1,х2,y1,y2 распределены равномерно).

Ответ я не помню, но он очень длинный.

Так вот, аналитический же переход от простой задачи к сложной: Вы ведь на самом деле ищете распределение минимума (ro) в выборке размером (N-1). Поэтому CDF(rо)_сложный = (CDF(rо)_простоц)^(N-1). Для больших N есть простая асимптотика, это будет так называемое распределение экстремальних значений, которых вроде как всего 3 разных (double exponential, Weibull и чего-то там еще, не помню). Посмотрите "Asymptotic Extreme Value distributions"