afstandsdistincties

Afstandsdistincties is een term uit de combinatorische geometrie die verwijst naar de verzameling van onderscheiden afstanden die optreden binnen een configuratie van punten, meestal in het vlak of in de Euclidische ruimte. Voor een eindige verzameling P van n punten in het vlak wordt D(P) gedefinieerd als de verzameling van alle afstanden tussen paren punten uit P: D(P) = { dist(p, q) | p, q ∈ P, p ≠ q }. De grootte van D(P) geeft aan hoeveel verschillende afstanden er voorkomen in de configuratie.

Belangrijkste vraag is hoe klein de kaart van afstanden kan zijn als het aantal punten toeneemt. De probleemschetsing werd in de literatuur vooral toegespitst op het vlak: hoeveel verschillende afstanden kunnen n punten maximaal of minimaal opleveren? Deze vraag staat bekend als het distinct distances probleem, en werd oorspronkelijk door Paul Erdős in de jaren zeventig opgeworpen.

Een van de belangrijkste doorbraken kwam met de bewijsvoering van Guth en Katz in 2010, die aantonen dat elke puntverzameling van n punten in het vlak minstens proportional tot n / log n verschillende afstanden bepaalt. Deze afmeting ligt dichter bij de conjectuur dan eerdere resultaten. Erdős’ oorspronkelijke intuïtie suggereerde een orde van grootte van ongeveer n / √log n, hoewel de exacte orde van magnitude nog niet volledig bewezen is.

Naast het vlak is er onderzoek naar afstandsdistincties in hogere dimensies en naar varianten, bijvoorbeeld het tellen van afstanden binnen specifieke configuraties of onder andere metrische ruimtes. Toepassingen komen voor in computationale geometrie, patroonherkenning en netwerktheorie, waar de structuur van afstanden van belang kan zijn voor detectie en optimalisatie.