home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15157 < prev    next >
Encoding:
Text File  |  1992-11-18  |  1.3 KB  |  32 lines
  1. Newsgroups: sci.math,tum.questions
  2. Path: sparky!uunet!usc!zaphod.mps.ohio-state.edu!darwin.sura.net!paladin.american.edu!news.univie.ac.at!news.tu-graz.ac.at!iaik!gwoeging
  3. From: gwoeging@iaik.wu-wien.ac.at (Guestaccount G.Woeginger)
  4. Subject: Re: Minimum number of lines that cover a set of points
  5. Message-ID: <1992Nov18.105945.16142@news.tu-graz.ac.at>
  6. Sender: news@news.tu-graz.ac.at (USENET News System)
  7. Nntp-Posting-Host: fiaikss04.tu-graz.ac.at
  8. Organization: Angewandte Informationsverabeitung und Kommunikationstechnologien, TU-Graz
  9. Date: Wed, 18 Nov 92 10:59:45 GMT
  10. Lines: 20
  11.  
  12. In article <1992Nov17.163800.21271@news.lrz-muenchen.de> Matthias Sauer writes:
  13. >
  14. >I am looking for an algorithm for the following problem:
  15. >
  16. >    Given a set P of points in the plane find a minimal 
  17. >    number of straight lines such that every p in P is
  18. >    on at least one of these lines.
  19. >
  20. >I am almost sure that there is some standard algorithm for this problem,
  21. >but I could not find any. Please send an e-mail to:
  22. >     sauer@nws.e-technik.tu-muenchen.de
  23. >or post an article in sci.math or tum.questions
  24.  
  25. This problem was shown to be NP-complete in the beginning of the 1980ies
  26. by van Emde Boas.  I think his paper was called "Another NP-completeness
  27. result" or something like this, and it is also mentioned in one of 
  28. Johnson's NP-completeness columns.
  29.  
  30. Gerhard Woeginger
  31.  
  32.