Abstrakt. Dynamiska kartor som möjliggör kontinuerliga kartrotationer, t.ex. på mobila enheter, stöter på nya problem som inte syns i statisk kartmärkning tidigare. Vi studerar följande dynamiska kartmärkningsproblem: Ingången är en statisk, märkt karta, d.v.s. en uppsättning P punkter i planet med bifogade icke-överlappande horisontella rektangulära etiketter. Målet är att hitta en konsekvent märkning av P under rotation som maximerar antalet synliga etiketter för alla rotationsvinklar så att etiketterna förblir horisontella medan kartan roteras. En märkning är konsekvent om ett enda aktivt intervall av vinklar väljs för varje etikett så att etiketter varken skär varandra ellerockludera punkter i P i någon rotationsvinkel. Vi introducerar först en allmän modell för märkning av roterande kartor och härleder grundläggande geometriska egenskaper hos konsekventa lösningar. Vi visar NPfullständighet av det aktiva intervallet maximeringsproblem även för unitsquare etiketter. Vi lägger sedan fram en approximation av konstanta faktorer för detta problem som bygger på line staffbing, och förfinar det ytterligare till ett effektivt polynom-tids approximationssystem (EPTAS). Slutligen utvidgar vi EPTAS till den mer allmänna inställningen av rektangulära etiketter med begränsad storlek och proportion.
De visade först att ARO-problemet är NP-hård i den inställningen och införde en effektiv polynom-tid-approximation system (EPTAS) för unitheight rektanglar REF.
Consistent Labeling of Rotating Maps
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}