Vi studerar problemet med att anpassa så många punkter som möjligt horisontellt, vertikalt eller diagonalt, när varje punkt tillåts placeras var som helst i sin egen, givna region. Olika former av placeringsregioner och olika uppsättningar av anpassningsinriktningar beaktas också. Mer allmänt antar vi att en graf ges på punkterna, och endast anpassningarna av punkter som är anslutna i grafräkningen. Vi visar att för plana grafer problemet är NP-hård, och vi ger oåtkomliga resultat för allmänna grafer. För träd och plana grafer ger vi approximativa algoritmer vars prestanda beror på form av de givna regionerna och uppsättningen av orienteringar. När de orienteringar som ska beaktas är de som ges av axlarna och regionerna är axelparallell rektangelr, får vi ett polynom tid approximationsschema.
Cabello och van Kreveld REF studerade approximationsalgoritmer för att justera punkter octililinearly, där varje punkt kan placeras var som helst i en lokalt definierad region.
Approximation algorithms for aligning points
{'venue': "SCG '03", 'journal': None, 'mag_field_of_study': ['Computer Science']}