home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / theory / 1822 < prev    next >
Encoding:
Text File  |  1992-08-25  |  1.3 KB  |  37 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!cs.utexas.edu!torn!watserv2.uwaterloo.ca!watmath!neumann.uwaterloo.ca!alopez-o
  3. From: alopez-o@neumann.uwaterloo.ca (Alex Lopez-Ortiz)
  4. Subject: Re: A sorting Exercise
  5. Message-ID: <BtK448.Axx@math.uwaterloo.ca>
  6. Sender: news@math.uwaterloo.ca (News Owner)
  7. Organization: University of Waterloo
  8. References:  <1992Aug25.184708.352@dartvax.dartmouth.edu>
  9. Date: Tue, 25 Aug 1992 20:40:55 GMT
  10. Lines: 25
  11.  
  12. In article <1992Aug25.184708.352@dartvax.dartmouth.edu>, scot@moosilauke.dartmouth.edu (Scot Drysdale) writes:
  13. > The question about sorting a sequence on a closed loop with every crossing
  14. > labeled is called Jordan Sorting (from the Jordan Curve theorem, I assume).
  15. > It can be done in linear time.  See
  16. > 
  17. > K. Hoffman, K. Mehlhorn, P. Rosenstiehl, and R. E. Tarjan, "Sorting
  18. > Jordan Sequences in Linear Time," Proc. Symp. Computational Geometry,
  19. > pp. 196-203 (1985).
  20. > 
  21. > It was to appear in Information and Control in 1986, but I don't have a
  22. > reference.
  23.  
  24. Sorting Jordan Sequences in Linear Time Using Level-Linked Search Trees
  25.  
  26. Vol 68
  27.  
  28. 1986 
  29.  
  30. Information and Control
  31.  
  32.  
  33. -- 
  34. Alex Lopez-Ortiz                              alopez-o@maytag.UWaterloo.ca
  35. Deparment of Computer Science                       University of Waterloo
  36. Waterloo, Ontario                                                   Canada
  37.