Maior célula em um arranjo

10

Q . Qual é a complexidade de encontrar a maior célula delimitada por volume em um arranjo de hiperplanos na dimensão d ?nd

Sinto que deveria saber disso ... Mas não estou encontrando uma referência definitiva.

É ? E a especialização d = 2 : a maior célula delimitada por área em um arranjo de linhas?Ω(nd)d=2

Joseph O'Rourke
fonte

Respostas:

6

De alguma forma, fazer melhor que parece difícil. Se a célula for significativamente maior que o tamanho médio esperado, pode-se usar a amostragem para encontrá-la. Formalmente, assuma que as células delimitadas (no plano) formam um polígono da área 1 (esse polígono Q pode ser calculado em tempo quase linear no plano). Suponha que a maior célula delimitada C, no arranjo de linhas, tenha a área α 1 / seja o conjunto de pontos resultante. Com alta probabilidade, um dos pontos cai dentro de C , e o cálculo de todas as faces do arranjo que contém os pontos de P leva O ( (O(nd)1 1QC . Amostra, m = ( log n ) / α pontos de Q - e deixe Pα1 1/n2m=(registron)/αQPCP hora usando magia padrão (isto é, algoritmos para calcular muitas faces no arranjo de linhas).O((n2/3m2/3+n+m)poeuyeuog)

αO((n+1 1/α+n2/3/α2/3)poeuyeuogn)αQ

Sariel Har-Peled
fonte
11
α1 1/n2