A polynomial time solution for labeling a rectilinear map

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A polynomial time solution for labeling a rectilinear map

Full text

Pdf (712 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the thirteenth annual symposium on Computational geometry table of contents

Nice, France

Pages: 451 - 453

Year of Publication: 1997

ISBN:0-89791-878-9

Authors

Chung Keung Poon	Dept. of Computer Science, City University of Hong Kong
Binhai Zhu	Dept. of Computer Science, City University of Hong Kong
Franis Chin	Dept. of Computer Science, University of Hong Kong

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 11, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/262839.263079 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	BC94	D. Beus and D. Crockett. Automated production of 1:24,000 scale quadrangle maps. In Proc. 199# ASPRS/A CSM Annual Convention and Exposition, volume 1, pages 94-99, 1994.
	CMS93	J. Christensen, J. Marks, and S. Shieber. Algorithms for cartographic label placement. In Proc. 1993 ASPRS/A CSM Annual Convention and Exposition, volume 1, pages 75-89, 1993.
	DF92	Jeffrey S. Doerschler , Herbert Freeman, A rule-based system for dense-map name placement, Communications of the ACM, v.35 n.1, p.68-79, Jan. 1992 [doi>10.1145/129617.129620]
	DMMMZ97	Srinivas Doddi , Madhav V. Marathe , Andy Mirzaian , Bernard M. E. Moret , Binhai Zhu, Map labeling and its generalizations, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.148-157, January 05-07, 1997, New Orleans, Louisiana, United States
	EIS76	S. Even, A. Itai and A. Shamir. On the complexity of timetable and multicommodity flow problem. SIAM J. Comput., 5:691-703, 1976.
	FW91	Michael Formann , Frank Wagner, A packing problem with applications to lettering of maps, Proceedings of the seventh annual symposium on Computational geometry, p.281-288, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109680]
	Imh75	E. Imhof. Positioning names on maps. The American Cartographer, 2:128-144, 1975.
	Jon89	Christopher B. Jones, Cartographic Name Placement with Prolog, IEEE Computer Graphics and Applications, v.9 n.5, p.36-47, September 1989 [doi>10.1109/38.35536]
	KR92	Donald E. Knuth , Arvind Raghunathan, The problem of compatible representatives, SIAM Journal on Discrete Mathematics, v.5 n.3, p.422-427, Aug. 1992 [doi>10.1137/0405033]
	PS85	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	Wag94	Frank Wagner, Approximate map labeling is in &OHgr;(n log n), Information Processing Letters, v.52 n.3, p.161-165, Nov. 11, 1994 [doi>10.1016/0020-0190(94)90001-9]
	WW95	Frank Wagner , Alexander Wolff, Map labeling heuristics: provably good and practically useful, Proceedings of the eleventh annual symposium on Computational geometry, p.109-118, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220291]
	Yo72	P. Yoeli. The logic of automated map lettering. The Cartographic Journal, 9:99-108, 1972.

CITED BY 3

	Sasanka Roy , Partha P. Goswami , Sandip Das , Subhas C. Nandy, Optimal algorithm for a special point-labeling problem, Information Processing Letters, v.89 n.2, p.91-98, 31 January 2004
	Frank Nielsen, On point covers of c-oriented polygons, Theoretical Computer Science, v.263 n.1-2, p.17-29, July 28 2001
	Stefan Maass , Jürgen Düllner, Embedded labels for line features in interactive 3D virtual environments, Proceedings of the 5th international conference on Computer graphics, virtual reality, visualisation and interaction in Africa, October 29-31, 2007, Grahamstown, South Africa