home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15172 < prev    next >
Encoding:
Text File  |  1992-11-18  |  1.3 KB  |  32 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!sun-barr!cs.utexas.edu!zaphod.mps.ohio-state.edu!malgudi.oar.net!caen!spool.mu.edu!darwin.sura.net!haven.umd.edu!news.umbc.edu!venus.cs.umbc.edu!piatko
  3. From: piatko@venus.cs.umbc.edu (Christine Piatko)
  4. Subject: Re: Minimum number of lines that cover a set of points
  5. Message-ID: <1992Nov18.162310.18795@umbc3.umbc.edu>
  6. Summary: NP-complete
  7. Sender: newspost@umbc3.umbc.edu (News posting account)
  8. Organization: University of Maryland Baltimore Campus, Computer Science Department
  9. References: <1992Nov17.163800.21271@news.lrz-muenchen.de>
  10. Date: Wed, 18 Nov 1992 16:23:10 GMT
  11. Lines: 19
  12.  
  13. > I am looking for an algorithm for the following problem:
  14. > 
  15. >     Given a set P of points in the plane find a minimal 
  16. >     number of straight lines such that every p in P is
  17. >     on at least one of these lines.
  18. > 
  19. >      sauer@nws.e-technik.tu-muenchen.de
  20.  
  21. Finding the *minimum* number of lines to cover points was shown to
  22. be NP-hard (NP-complete if you ask "Is there a way to cover the
  23. points with k lines?") in the following paper:
  24.  
  25. \bibitem[MT82]{MT}
  26. N.~Megiddo and A.~Tamir.
  27. \newblock On the complexity of locating linear facilities in the plane.
  28. \newblock {\em Operations Research Letters}, 1(5):194--197, November 1982.
  29.  
  30. Christine Piatko
  31. piatko@cs.umbc.edu
  32.