The Daily Static
  The Daily Static
UF Archives
Register
UF Membership
Ad Free Site
Postcards
Community
Geekfinder
UFie Gear
Advertise on UF
Forum Rules
& FAQ

Username

Password


Create a New Account

  
 

Back to UserFriendly Strip Comments Index
geometry problem by dennismv 2007-07-29 16:44:09
suppose you have a limited number of randomly distributed dots in a 2 dimensional Eucledian space.

Given a certain distance d, draw a circle with radius d around one of the dots. Some nearby dots may now be on or within this circle. Remove this circle and all the dots inside of it, including the original dot. Repeat until all the dots are gone.

Question: is this a common problem ? does it have a name ? is there a way of removing dots as to minimize then number or resulting circles ?
[ Reply ]
  Interesting problem. by Arachnid2007-07-29 17:03:51
    NP complete you say? by Michiel2007-07-29 17:14:37
      I think there is. by imperito2007-07-29 17:19:33
        yeah it could be that by dennismv2007-07-29 17:38:07
          Sure there is... by imperito2007-07-29 17:40:50
            aahhhhhhhhhhhh by dennismv2007-07-29 17:44:47
              One thing, though.... by imperito2007-07-29 17:50:44
                I'd say the first one by dennismv2007-07-29 19:50:24
                  Hmm... by imperito2007-07-29 20:03:11
                    wow that is amazing ! by dennismv2007-07-29 20:45:00
    thanks by dennismv2007-07-29 17:29:27
  Hm.. Might be NP hard. by Michiel2007-07-29 17:06:57
  Hehehe.. by MrTrick2007-07-29 17:23:26
    hehe close but no cigar :) by dennismv2007-07-29 17:30:35
    when d becomes infinite all points by joecrouse2007-07-29 17:33:20
  "Nearest Neighbours", repeatedly? by williamashbless2007-07-29 17:34:02
    I'm pretty sure it is Dominating Set (n/t) by imperito2007-07-29 17:37:19
  are you really drawing a circle or by lillylight2007-07-29 17:38:39
    The problem is 2D. by Didactylos2007-07-29 17:48:15
      I see... (n/t) by lillylight2007-07-29 17:50:34

 

[Todays Cartoon Discussion] [News Index]

Come get yer ARS (Account Registration System) Source Code here!
All images, characters, content and text are copyrighted and trademarks of J.D. Frazer except where other ownership applies. Don't do bad things, we have lawyers.
UserFriendly.Org and its operators are not liable for comments or content posted by its visitors, and will cheerfully assist the lawful authorities in hunting down script-kiddies, spammers and other net scum. And if you're really bad, we'll call your mom. (We're not kidding, we've done it before.)