home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / theory / 1819 < prev    next >
Encoding:
Internet Message Format  |  1992-08-25  |  901 b 
  1. Path: sparky!uunet!elroy.jpl.nasa.gov!usc!rpi!bu.edu!dartvax!moosilauke!scot
  2. From: scot@moosilauke.dartmouth.edu (Scot Drysdale)
  3. Newsgroups: comp.theory
  4. Subject: A sorting Exercise
  5. Message-ID: <1992Aug25.184708.352@dartvax.dartmouth.edu>
  6. Date: 25 Aug 92 18:47:08 GMT
  7. Sender: news@dartvax.dartmouth.edu (The News Manager)
  8. Organization: Dartmouth College, Hanover, NH
  9. Lines: 16
  10. Originator: scot@moosilauke
  11.  
  12. The question about sorting a sequence on a closed loop with every crossing
  13. labeled is called Jordan Sorting (from the Jordan Curve theorem, I assume).
  14. It can be done in linear time.  See
  15.  
  16. K. Hoffman, K. Mehlhorn, P. Rosenstiehl, and R. E. Tarjan, "Sorting
  17. Jordan Sequences in Linear Time," Proc. Symp. Computational Geometry,
  18. pp. 196-203 (1985).
  19.  
  20. It was to appear in Information and Control in 1986, but I don't have a
  21. reference.
  22.  
  23. -- 
  24.  
  25. Scot Drysdale
  26. Dartmouth College
  27. scot.drysdale@dartmouth.edu
  28.