Sorting Jordan sequences in linear time

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Sorting Jordan sequences in linear time

Full text

Pdf (403 KB)

Source

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

Baltimore, Maryland, United States

Pages: 196 - 203

Year of Publication: 1985

ISBN:0-89791-163-6

Authors

Kurt Hoffmann	Universität des Saarlandes, Saarbrücken, GERMANY
Kurt Mehlhorn	Universität des Saarlandes, Saarbrücken, GERMANY
Pierre Rosenstiehl	Centre de Mathdmaticue Sociale, Paris, FRANCE
Robert E. Tarjan	AT&T Bell Laboratories, Murray Hill, NJ

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): 10, Downloads (12 Months): 30, Citation Count: 2

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/323233.323259 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.

	1	[1] M. R. BROWN and R. E. TARJAN, "Design and analysis of a data structure for representing sorted lists", SIAM J. Comput. 9, (1980), 594-614.
	2	[2] H. EDELSBRUNNER, Problem P36, Bull. EATCS 21, (October 1983), 195.
	3	[3] M. L. FREDMAN, "How good is the information theory bound in sorting?", Theor. Comp. Sci. 1, (1976), 355-361.
	4	[4] K. HOFFMANN and K. MEHLHORN, "Intersecting a line and a simple polygon", Bull. EATCS 22, (February 1984), 120-121.
	5	[5] S. HUDDLESTON and K. MEHLHORN, "A new data structure for representing sorted lists", Acta Info. 17, (1982), 157-184.
	6	[6] M. IRI, Private communication.
	7	[7] D. MAIER and C. SALVETER, "Hysterical B-trees", Info. Proc. Lett. 12, (1981), 199-202.
	8	[8] K. MEHLHORN, Data Structures and Efficient Algorithms, vol. 1, Sorting and Searching, Springer Verlag, (1984).
	9	[9] "Planar permutations defined by two intersecting Jordan curves", Graph Theory and Combinatorics, Academic Press, London, (1984), 259-271.
	10	[10] R. E. TARJAN, "Amortized computational complexity", SIAM J. Alg. Disc. Meth., (to appear).

CITED BY 2

	R E Tarjan , C J Van Wyk, A linear-time algorithm for triangulating simple polygons, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.380-388, May 28-30, 1986, Berkeley, California, United States
	David Dobkin , Leonidas Guibas , John Hershberger , Jack Snoeyink, An efficient algorithm for finding the CSG representation of a simple polygon, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.31-40, Aug. 1988