Kartmärkning är ett problem med att placera etiketter på motsvarande grafiska funktioner på en karta. Det finns två optimeringsproblem: problemet med etikettnummer maximering och problemet med etikettstorlek maximering. I allmänhet är båda problemen NP-hårda för statiska kartor. Nyligen har den utbredda användningen av flera tillämpningar, såsom personliga kartsystem, ökat betydelsen av dynamiska kartor och problemet med maximering av etiketter för dynamiska fall har studerats. I det här dokumentet överväger vi problemet med maximering av etikettens storlek för punkter på roterande kartor. Vår modell är som följer. För varje etikett väljs en punkt inuti etiketten eller på dess gräns som ankarpunkt. Varje etikett placeras så att ankarpunkten sammanfaller med motsvarande punkt på kartan. Samtidigt som kartan roterar helt från 0 till 2π placeras etiketterna horisontellt enligt kartans vinkel. Vårt problem består i att hitta den maximala skalfaktorn för etiketterna så att etiketterna inte skär varandra, och att bestämma platsen för ankarpunkterna. Vi föreslår en O(n log n)-tid och O(n)-rymd algoritm för fallet där varje ankarpunkt är inne i etiketten. Dessutom, om etiketterna är av enhet-höjd (eller enhet-bredd) och ankarpunkterna är på gränsen, presenterar vi också en O (n log n)-tid och O (n)-rymd algoritm.
REF beaktade problemet med maximering av etikettstorlek för roterande kartor, där målet är att hitta den maximala teckenstorleken för vilken alla etiketter kan vara ständigt synliga under rotationen.
Polynomial Time Algorithms for Label Size Maximization on Rotating Maps
{'venue': 'CCCG', 'journal': None, 'mag_field_of_study': ['Computer Science']}