[{"type":"article-journal","title":"Consistent labeling of rotating maps","issued":{"date-parts":[["2016"]]},"volume":"7","issue":"1","page":"308-331","container-title":"Journal of computational geometry","DOI":"10.20382\/jocg.v7i1a15","author":[{"family":"Gemsa","given":"Andreas"},{"family":"N\u00f6llenburg","given":"Martin"},{"family":"Rutter","given":"Ignaz"}],"ISSN":"1920-180X","abstract":"Dynamic maps that allow continuous map rotations, for example, on mobile\r\ndevices, encounter new geometric labeling issues unseen in static maps before. We study the\r\nfollowing dynamic map labeling problem: The input is an abstract map consisting of a set P\r\nof points in the plane with attached horizontally aligned rectangular labels. While the map\r\nwith the point set P is rotated, all labels remain horizontally aligned. We are interested in\r\na consistent labeling of P under rotation, i.e., an assignment of a single (possibly empty)\r\nactive interval of angles for each label that determines its visibility under rotations such\r\nthat visible labels neither intersect each other (soft conflicts) nor occlude points in P at any\r\nrotation angle (hard conflicts). Our goal is to find a consistent labeling that maximizes the\r\nnumber of visible labels integrated over all rotation angles.\r\nWe first introduce a general model for labeling rotating maps and derive basic geometric\r\nproperties of consistent solutions. We show NP-hardness of the above optimization\r\nproblem even for unit-square labels. We then present a constant-factor approximation for\r\nthis problem based on line stabbing, and refine it further into an efficient polynomial-time\r\napproximation scheme (EPTAS).","kit-publication-id":"1000083097"}]