File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A polynomial time solution for labeling a rectilinear map

TitleA polynomial time solution for labeling a rectilinear map
Authors
KeywordsComputational Geometry
Map Labeling
Issue Date1998
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/ipl
Citation
Information Processing Letters, 1998, v. 65 n. 4, p. 201-207 How to Cite?
AbstractGiven a rectilinear map consisting of n disjoint line segments, the corresponding map labeling problem is to place a maximum width rectangle at each segment using one of the three natural ways. In a recent paper, it is shown that if all segments are horizontal then the problem can be solved in optimal Θ (n log n) time. For the general problem a factor-2 approximate solution and a Polynomial Time Approximation Scheme are also proposed. In this paper, we show that the general problem is polynomially solvable with a nontrivial use of 2SAT and the solution can be even generalized to the case of allowing k natural placements for each segment, where k is any fixed constant. We believe this technique can be also used to solve other geometric packing problems. © 1998 Elsevier Science B.V.
Persistent Identifierhttp://hdl.handle.net/10722/152268
ISSN
2023 Impact Factor: 0.7
2023 SCImago Journal Rankings: 0.404
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorPoon, CKen_US
dc.contributor.authorBinhai, Zen_US
dc.contributor.authorChin, Fen_US
dc.date.accessioned2012-06-26T06:36:51Z-
dc.date.available2012-06-26T06:36:51Z-
dc.date.issued1998en_US
dc.identifier.citationInformation Processing Letters, 1998, v. 65 n. 4, p. 201-207en_US
dc.identifier.issn0020-0190en_US
dc.identifier.urihttp://hdl.handle.net/10722/152268-
dc.description.abstractGiven a rectilinear map consisting of n disjoint line segments, the corresponding map labeling problem is to place a maximum width rectangle at each segment using one of the three natural ways. In a recent paper, it is shown that if all segments are horizontal then the problem can be solved in optimal Θ (n log n) time. For the general problem a factor-2 approximate solution and a Polynomial Time Approximation Scheme are also proposed. In this paper, we show that the general problem is polynomially solvable with a nontrivial use of 2SAT and the solution can be even generalized to the case of allowing k natural placements for each segment, where k is any fixed constant. We believe this technique can be also used to solve other geometric packing problems. © 1998 Elsevier Science B.V.en_US
dc.languageengen_US
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/iplen_US
dc.relation.ispartofInformation Processing Lettersen_US
dc.rightsInformation Processing Letters. Copyright © Elsevier BV.-
dc.subjectComputational Geometryen_US
dc.subjectMap Labelingen_US
dc.titleA polynomial time solution for labeling a rectilinear mapen_US
dc.typeArticleen_US
dc.identifier.emailChin, F:chin@cs.hku.hken_US
dc.identifier.authorityChin, F=rp00105en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1016/S0020-0190(98)00002-7-
dc.identifier.scopuseid_2-s2.0-0031998590en_US
dc.identifier.hkuros31115-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0031998590&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume65en_US
dc.identifier.issue4en_US
dc.identifier.spage201en_US
dc.identifier.epage207en_US
dc.identifier.isiWOS:000072942600007-
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridPoon, CK=7202673523en_US
dc.identifier.scopusauthoridBinhai, Z=7801692615en_US
dc.identifier.scopusauthoridChin, F=7005101915en_US
dc.identifier.issnl0020-0190-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats