Full metadata record
DC FieldValueLanguage
dc.contributor.authorYu, Kuen-Linen_US
dc.contributor.authorLiao, Chung-Shouen_US
dc.contributor.authorLee, D. T.en_US
dc.date.accessioned2014-12-08T15:07:02Z-
dc.date.available2014-12-08T15:07:02Z-
dc.date.issued2007en_US
dc.identifier.isbn978-3-540-73813-8en_US
dc.identifier.issn0302-9743en_US
dc.identifier.urihttp://hdl.handle.net/11536/5512-
dc.description.abstractIn this paper, we consider a map labeling problem to maximize the number of independent labels in the plane. We first investigate the point labeling model that each label can be placed on a given set of anchors on a horizontal line. It is known that most of the map labeling decision models on a single line (horizontal or slope line) can be easily solved. However, the label number maximization models are more difficult (like 2SAT vs. MAX-2SAT). We present an O(n log Delta) time algorithm for the four position label model on a horizontal line based on dynamic programming and a particular analysis, where n is the number of the anchors and Delta is the maximum number of labels whose intersection is nonempty. As a contrast to Agarwal et al.'s result [Comput. Geom. Theory Appl. 11 (1998) 209-218] and Chan's result [Inform. Process. Letters 89(2004) 19-23] in which they provide (1 + 1/k)-factor PTAS algorithms that run in O(nlogn + n(2k-1)) time and O(n log n + n Delta(k-1) time respectively for the fixed-height rectangle label placement model in the plane, we extend our method to improve their algorithms and present a (1 + 1/k)-factor PTAS algorithm that runs in O(n log n+kn log(4) Delta + Delta (k-1)) time using O(k Delta log(4) + k Delta(k-1)) storage.en_US
dc.language.isoen_USen_US
dc.titleMaximizing the number of independent labels in the planeen_US
dc.typeProceedings Paperen_US
dc.identifier.journalFrontiers in Algorithmics, Proceedingsen_US
dc.citation.volume4613en_US
dc.citation.spage136en_US
dc.citation.epage147en_US
dc.contributor.department資訊工程學系zh_TW
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.identifier.wosnumberWOS:000248536400013-
Appears in Collections:Conferences Paper