Кіріспе

Дискретті геометрия және сәйкессіздік теориясында Хайльбронн үшбұрышы мәселесі – жазықтықта нүктелерді орналастыру, кішкентай ауданы бар үшбұрыштардың пайда болуын болдырмау мәселесі. Ол Ханс Хайльброннның есімімен аталады, ол қандай да бір аумақта нүктелер қалай орналасса да, ең кішкентай үшбұрыштың ауданы нүктелер санының квадратына кері пропорционал болады деп болжаған. Оның болжамы дұрыс емес екені дәлелденді, бірақ ең кішкентай үшбұрыштың асимптотикалық өсу жылдамдығы әлі белгісіз.

Анықтама

Гейльбронн үшбұрышы мәселесі жазықтықтағы пішіннің ішінде – мысалы, бірлік квадраттың немесе бірлік дискінің – берілген сан үшін нүктелерді орналастыруға қатысты. Әрбір үштік нүкте үшбұрыштың үш төбесін құрайды, ал осы үшбұрыштардың арасында мәселе ауданы бойынша ең кіші үшбұрышты анықтауға қатысты. Нүктелердің әртүрлі орналасуы әртүрлі ең кіші үшбұрыштарға әкеледі, және мәселе мынаны сұрайды: ең кіші үшбұрыштың ауданын барынша арттыру үшін нүктелерді қалай орналастыру керек?

Көбінесе, пішін жазықтықтағы компакт жиын деп есептелуі мүмкін, яғни ол бастапқы нүктеден шектеулі қашықтықта қалады және нүктелер оның шекарасында орналасуы мүмкін. Бұл мәселені зерттеуде пішін көбінесе нөлдік емес ауданы бар дөңес жиын болып қарастырылады. Егер орналастырылған үш нүкте бір түзуде жатса, олар ауданы нөлге тең дегенеративті үшбұрышты құрайды деп есептеледі, сондықтан ең кіші үшбұрышты максималдайтын орналасуларда бір түзуде жатқан үш нүкте болмайды. Пішіннің компакттығы болжамы, нүктелердің оңтайлы орналасуы бар екенін білдіреді, тек оңтайлылыққа жақындасатын орналасулар тізбегі емес. саны осы оңтайлы орналасудағы ең кіші үшбұрыштың ауданы ретінде анықталуы мүмкін. Мысалы, бірлік квадратта алты нүкте көрсетілген. Бұл алты нүкте 20 түрлі үшбұрышты құрайды, олардың төртеуі суретте көлеңкеленген. Осы 20 үшбұрыштың 6-ы, оның ішінде екі көлеңкеленгені, 1/8 ауданына ие, ал қалған 14 үшбұрыштың ауданы үлкен. Бұл бірлік квадраттағы алты нүктелердің оңтайлы орналасуы: басқа барлық орналасулар кемінде 1/8 немесе одан кіші ауданы бар үшбұрышты құрайды. Сондықтан,

Зерттеушілер белгілі пішіндер мен нүктелердің шағын саны үшін -ның мәнін зерттегенімен, Гейльбронн оның асимптотикалық мінез-құлқына көбірек қызығушылық танытты: егер пішін өзгермейтін болса, бірақ өзгерсе, ең кіші үшбұрыштың ауданы қалай өзгереді? Яғни, Гейльбронн сұрағы -ның өсу қарқынына қатысты. Кез келген екі пішін үшін және сандары тек тұрақты фактормен ғана ерекшеленеді, себебі пішін ішіндегі нүктелердің кез келген орналасуы аффиндік түрлендіру арқылы масштабталуы мүмкін, бұл ең кіші үшбұрыштың ауданын тек тұрақты түрде өзгертеді. Сондықтан, өсу қарқынының шегінде пропорционалдық тұрақты алынып тасталса, пішіннің таңдалуы маңызсыз және төменгі индекстің өзі алынып тасталуы мүмкін.

Өзгеше пішіндер мен сандар

16 нүктеге дейін квадраттағы нүктелердің ең оңтайлы орналасуын зерттеді. Голдбергтің алты нүктеге дейінгі құрылыстары квадраттың шекарасында орналасқан және тұрақты көпбұрыштың төбелерінің аффиндік түрлендіруін құру үшін жиналған. Үлкен мәндер үшін , Голдбергтің шектері жақсартылды, және осы мәндердегі шешімдер квадраттың ішкі нүктелерін қамтиды. Бұл құрылыстар жеті нүктеге дейін ең оңтайлы деп дәлелденді. Дәлелдеу үшін нүктелердің мүмкін орналасу конфигурациясының кеңістігі компьютерлік іздеу арқылы 226 түрлі кіші мәселеге бөлінді, содан кейін сызықтық емес бағдарламалау әдістері қолданылып, 225 жағдайда ең жақсы орналасу белгілі шектен нашар екені көрсетілді. Қалған жағдайда, оның ішінде ең оңтайлы шешімнің өзі, символдық есептеу әдістері арқылы оңтайлы екені дәлелденді. Бірлік шаршыдағы 7–12 нүктелерге арналған ең жақсы белгілі шешімдер төменде келтірілген, олар симуляцияланған қайнату арқылы табылды; жеті нүктеге арналған орналасу ең оңтайлы екені белгілі. Белгілі бір пішін үшін ең оңтайлы орналасуларды іздеудің орнына, белгілі бір нүктелер саны үшін ең оңтайлы пішін іздеуге болады. Бірдей ауданы бар дөңес пішіндердің ішінде, тұрақты алтыбұрыш максимизациялайды; бұл пішін үшін , алты нүкте алтыбұрыштың төбелерінде ең оңтайлы орналасқан. Бірлік ауданы максимизациялайтын дөңес пішіндерде…