algorithm - Placing a point to minimise distance from the farthest point -

-

i have question,

given set of points , how place point constraint distance farthest point small possible?.

this in reference this problem. not know how proceed. pointers anyone?

thanks

check out page. describes several methods this. http://www.personal.kent.edu/~rmuhamma/compgeometry/mycg/cg-applets/center/centercli.htm

in case link above ever dies, here's relevant part describes straight-forward method:

an o(n2)-time algorithm

  1. draw circle @ center, c, such points of given set lie within circle. clearly, circle can made smaller (or else have solution).
  2. make circle smaller finding point farthest center of circler, , drawing new circle same center , passing through point a. these 2 steps produce smaller enclosing circle. reason new circle smaller new circle still contains points of given set, except passes through farthest point, x, rather enclosing it.
  3. if circle passes through 2 or more points, proceed step 4. otherwise, make circle smaller moving center towards point a, until circle makes contact point b set.

  4. at stage, circle, c, passes through 2 or more points of given set. if circle contains interval (point-free interval) of arc greater half circle's circumference on no points lie, circle can made smaller. let d , e points @ ends of point-free interval. while keeping d , e on circle's boundary, reduce diameter of circle until have either case (a) or case (b).

    • case (a) diameter distance de.
      • we done!
    • case (b) circle c touches point set, f.
      • check whether there exits point-free arc intervals of length more half circumference of c.
      • if no such point-free arc intervals exit done!
    • else
      • goto step 4.
      • in case, 3 points must lie on arc less half circumference in length. repeat step 4 on outer 2 of 3 points on arc.

another page here, sample applet: http://www.sunshine2k.de/stuff/java/welzl/welzl.html


Comments

Post a Comment

Popular posts from this blog

c# - SVN Error : "svnadmin: E205000: Too many arguments" -

-
i trying reposotries using c# code process svncommand = null; var psi = new processstartinfo("svnadmin"); psi.redirectstandardoutput = true; psi.redirectstandarderror = true; psi.useshellexecute = false; psi.arguments= @"dump c:\repositories\myrepo > c:\temp\myrepodumpfile.dump"; using (svncommand = process.start(psi)) { var myoutput = svncommand.standardoutput; var myerror = svncommand.standarderror; debug.write("output :" + environment.newline + environment.newline + myoutput.readtoend() + environment.newline + "error :" + environment.newline + environment.newline + myerror.readtoend()); svncommand.close(); } when use dump command commandline svnadmin dump c:\repositories\myrepo > c:\temp\myrepodumpfile.dump it works fine when try ...
Read more

c# - Copy ObservableCollection to another ObservableCollection -

-
how copy observablecollection item observablecollection without reference of first collection? here observablecollection item value changes affecting both collections. code private observablecollection<ratemodel> _allmetalrate = new observablecollection<ratemodel>(); private observablecollection<ratemodel> _metalrateondate = new observablecollection<ratemodel>(); public observablecollection<ratemodel> allmetalrate { { return this._allmetalrate; } set { this._allmetalrate = value; notifypropertychanged("metalrate"); } } public observablecollection<ratemodel> metalrateondate { { return this._metalrateondate; } set { this._metalrateondate = value; notifypropertychanged("metalrateondate"); } } foreach (var item in metalrateondate) allmetalrate.add(item); what causing , how can solve it? you need clone object referenced item before it's a...
Read more

All overlapping substrings matching a java regex -

-
is there api method returns (possibly overlapping) substrings match regular expression? for example, have text string: string t = 04/31 412-555-1235; , , have pattern: pattern p = new pattern("\\d\\d+"); matches strings of 2 or more characters. the matches are: 04, 31, 412, 555, 1235. how overlapping matches? i want code return: 04, 31, 41, 412, 12, 55, 555, 55, 12, 123, 1235, 23, 235, 35. theoretically should possible -- there obvious o(n^2) algorithm enumerates , checks substrings against pattern. edit rather enumerating substrings, safer use region(int start, int end) method in matcher . checking pattern against separate, extracted substring might change result of match (e.g. if there non-capturing group or word boundary check @ start/end of pattern). edit 2 actually, it's unclear whether region() expect zero-width matches. specification vague, , experiments yield disappointing results. for example: string line = "xx90xx"; strin...
Read more