Как не вычислить наименьший круг, заключающий в себе конечный набор кругов

17

Предположим , что мы имеем конечное множество дисков в , и мы хотим вычислить наименьший диск , для которых . Стандартный способ сделать это состоит в использовании алгоритма Matoušek, Шарир и Welzl [1] , чтобы найти базис из , и пусть , самый маленький диск , содержащий . Диск может быть вычислен алгебраически с использованием того факта, что, поскольку B является базисом, каждый диск в B касается \ langle B \ rangle .LR2DLDBLD=BBBBBB

( BL является основой из L , если B является минимальным , так что B=L Основа имеет не более трех элементов;. В целом для шаров в Rd основы не более d+1 элементов.)

Это рандомизированный рекурсивный алгоритм следующим образом. (Но см. Ниже итеративную версию, которая может быть легче для понимания.)

Процедура : MSW(L,B)
Вход : конечные наборы дисков L , B , где B является базой ( B ).

  1. Если L= , возврат B .
  2. В противном случае выберите XL наугад.
  3. Пусть BMSW(L{X},B) .
  4. Если XB вернуть B .
  5. В противном случае верните MSW(L,B) , где B является базисом B{X} .

Используется в качестве MSW(L,) вычислить базис L .

Недавно у меня была причина реализовать этот алгоритм. После проверки правильности результатов в миллионах случайно сгенерированных тестовых случаев я заметил, что допустил ошибку в реализации. На последнем этапе я возвращал MSW(L{X},B) а не MSW(L,B) .

Несмотря на эту ошибку, алгоритм давал правильные ответы.


Мой вопрос: почему эта неправильная версия алгоритма дает правильные ответы здесь? Это всегда (доказуемо) работает? Если так, то это также верно для более высоких измерений?


Добавлено: некоторые заблуждения

Несколько человек предложили неверные аргументы о том, что модифицированный алгоритм тривиально корректен, поэтому здесь может быть полезно предотвратить некоторые заблуждения. Похоже, одно из распространенных ложных убеждений состоит в том, что . Вот контрпример к этому требованию. Для дисков как показано ниже (граница также показана красным):, б , с , д , е , б , е BMSW(L,B)a,b,c,d,ea,b,e

Диски а, б, в, д, е

мы можем иметь ; и обратите внимание, что :е с , d MSW({c,d},{a,b,e})={c,d}ec,d

наименьший вмещающий круг c и d не содержит e

Вот как это может произойти. Первое наблюдение состоит в том, что :MSW({c},{a,b,e})={b,c}

  • Мы хотим вычислитьMSW({c},{a,b,e})
  • ВыберитеX=c
  • ПустьB=MSW(,{a,b,e})={a,b,e}
  • Заметьте, чтоXB
  • Итак, пусть является базисомB { X } = { a , b , c , e }BB{X}={a,b,c,e}
  • Заметьте, чтоB={b,c}
  • Вернуть , то есть{ b , c }MSW({c},{b,c}){b,c}

Теперь рассмотрим .MSW({c,d},{a,b,e})

  • Мы хотим вычислитьMSW({c,d},{a,b,e})
  • ВыберитеX=d
  • ПустьB=MSW({c},{a,b,e})={b,c}
  • Заметьте, чтоXB
  • Итак, пусть является базисомB { X } = { b , c , d }BB{X}={b,c,d}
  • Заметьте, чтоB={c,d}
  • Вернуть , то есть{ c , d }MSW({c,d},{c,d}){c,d}

(Для определенности скажем, что все диски имеют радиус 2 и центрированы в , , , и соответственно.)( 30 , 5 ) ( 30 , 35 ) ( 10 , 5 ) ( 60 , 26 ) ( 5 , 26 )a,b,c,d,e(30,5)(30,35)(10,5)(60,26)(5,26)


Добавлено: итеративная презентация

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

Входные данные : список дисков Выход : ОсноваLL
L

  1. Пусть .B
  2. Перемешать случайно.L
  3. Для каждого в :LXL
  4.   Если :XB
  5.     Пусть - базис .B { X }BB{X}
  6.     Вернитесь к шагу 2.
  7. Возврат .B

Причина алгоритм завершается, между прочим, является то , что шаг 5 всегда увеличивает радиус - и есть лишь конечное число возможных значений .БBB

Насколько я вижу, модифицированная версия не имеет такой простой итеративной презентации. (Я пытался дать один в предыдущем редактировании этого поста, но это было неправильно - и дал неправильные результаты.)


Ссылка

[1] Иржи Матушек, Миха Шарир и Эмо Вельцль. Субэкспоненциальная оценка для линейного программирования. Algorithmica, 16 (4-5): 498–516, 1996.

Робин Хьюстон
источник
Во-первых, в вашей строке "Input: ..." Я думаю, что вы хотите "(из L)", а не "(из B)". Во-вторых, при возврате MSW (L- {X}, B '') вместо MSW (L, B '') ваш базис B '' определяется как базис [B 'union {X}], поэтому X все еще гарантированно покрывается MSW (L- {X}, B ''), даже если вы удалили его из набора.
ДжимN
Нет, я действительно имею в виду «(из B)», и B не обязательно является подмножеством L в рекурсивных вызовах. Элементы BL не обязательно покрываются MSW (L, B), как в этом примере bl.ocks.org/robinhouston/c4c9dffbe8bd069028cad8b8760f392c, где и (Нажмите маленькие кнопки со стрелками, чтобы выполнить вычисления).B = { a , b , e }L={a,b,c,d}B={a,b,e}
Робин Хьюстон,

Ответы:

1

Этот шаг удаления из перед продолжением рекурсии фактически улучшает алгоритм, потому что он удаляет уже добавленный из пула базовых кандидатов. Это всегда будет доказуемо работать, потому что это эквивалентно существующему алгоритму, и это также будет работать для более высоких измерений.L XXLX

Трассировка по алгоритму. Когда вы используете , есть и . Предположим, что мы выбрали его снова в шаге 2. Независимо от результата шага 3, всегда будет иметь , потому что рекурсивная функция имеет инвариант .X L X B B X B M S W ( L , B )MSW(L,B)XLXBBXBMSW(L,B)

Другими словами, ваше усовершенствование алгоритма сокращает до шага 3 в той части, где выбранX

Ларри Б.
источник
Это не правда, что в целом. Посмотрите на пример, связанный в моем комментарии к вопросу. BMSW(L,B)
Робин Хьюстон
В общем, это также не правда, что ! Вы имели в виду ? Я подозреваю, что если вы попытаетесь объяснить свой аргумент более строго, вы увидите, что он не работает. X B "XBXB
Робин Хьюстон
NB. В общем, это даже не правда, что . BMSW(L,B)
Робин Хьюстон
Я добавил раздел к вопросу, дающий контрпример к , так как несколько человек предположили, что это правда. BMSW(L,B)
Робин Хьюстон
1
О, я полностью пропустил это! . Да, этот ответ совершенно неверный. Должен ли я удалить это? B=BX
Ларри Б.