home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / theory / 1823 < prev    next >
Encoding:
Text File  |  1992-08-25  |  2.0 KB  |  50 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: <BtK5tM.DLF@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 21:17:45 GMT
  10. Lines: 38
  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.  
  22. Jordan Sequences are a bit different than those proposed by the original
  23. posting. In fact 6 1 5 4 3 2 is a jordan sequence corresponding to a 
  24. Jordan curve crossing the real line in 6 then at 1, 5, 4, 3, 2.
  25.  
  26. This sequence does not have a Jorden sequence traversing through them
  27. in the sense of the original posting.
  28.  
  29. >  I-----------------------------------I
  30. >  I                                   I
  31. >  I       I-------------------I       I                 
  32. >  I       I                   I       I                     
  33. >  I       I   I-----------I   I       I
  34. >  I       I   I           I   I       I
  35. >  I   I   I   I   I---I   I   I       I 
  36. >  I   I   I   I   I   I   I   I       I
  37. >=87==93===7==45==54==62==32==15=======I=====
  38. >  I   I   I   I   I   I   I   I       I
  39. >  I---I   I   I---I   I   I---I       I
  40. >          I           I               I
  41. >          I           I---------------I
  42. >          I
  43.  
  44. Hope it helps.
  45.  
  46. -- 
  47. Alex Lopez-Ortiz                              alopez-o@maytag.UWaterloo.ca
  48. Deparment of Computer Science                       University of Waterloo
  49. Waterloo, Ontario                                                   Canada
  50.