Vi ger e cient algoritmer för att beräkna en optimal uppdelning av en uppsättning punkter eller en uppsättning enkla polygoner i planet. I synnerhet ger vi en O(n 2 ) algoritm för att dela upp en uppsättning n punkter i två undergrupper för att minimera summan av omkretsen av konvexa skrov. Vi undersöker också problemen med att minimera maximum av omkretsen, eller summan / maximum av områdena, för det fall partitioneringen är en linje partitionering, framkallad av någon linje, och vi undersöker relaterade problem för uppdelning av polygoner.
Arbetet av Mitchell och Wynters REF studerade fyra smaker av problemet: minimera summan av omkretser, den maximala av omkretsen, summan av de områden som omges av stängsel, och den maximala av områdena.
Finding Optimal Bipartitions of Points and Polygons
{'venue': 'WADS', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}