Geometria Computacional com Primitivas Probabilisticamente Ruidosas

Uma nova pré-impressão explora algoritmos de geometria computacional sob operações primitivas probabilisticamente ruidosas. Muitos desses algoritmos dependem de primitivas que acessam coordenadas de entrada e as convertem em informações combinatórias. O artigo considera primitivas que produzem resultados incorretos aleatoriamente e investiga como obter resultados corretos com alta probabilidade sem perda significativa de eficiência. Descobriu-se que, para alguns problemas (como a construção do casco convexo), a lentidão devido à repetição pode ser evitada, enquanto para outros (como encontrar pares mais próximos), não pode. Isso se conecta a trabalhos anteriores sobre complexidade de comunicação usando comparações ruidosas para melhorar a eficiência.