c - Given centers, find minimum radius for set of circles such that they fully cover another -

-

i have following geometry problem: given circle center in origin - c(0, 0), , radius 1. inside circle given n points represent centers of n different circles. asked find minimum radius of small circles (the radius of circles equal) in order cover boundary of large circle.

the number of circles is: 3 ≤ n ≤ 10000 , problem has solved precision of p decimals 1 ≤ p ≤ 6.

for example:
n = 3 , p = 4

and coordinates:
(0.193, 0.722)
(-0.158, -0.438)
(-0.068, 0.00)

the radius of small circles is: 1.0686.

i have following idea problem implementing it. idea consists of binary search find radius , each value given binary search try , find intersection point between small circles , large one. each intersection have result arc. next step 'project' coordinates of arcs on x axis , y axis, result being number of intervals. if reunions of intervals x , y axis have result interval [-1, 1] on each axis, means circle covered.

in order avoid precision problems thought of searching between 0 , 2×10p, , taking radius 10p, eliminating figures after comma, problem figuring out how simulate intersection of circles , afterwards how see if reunion of resulting intervals form interval [-1, 1].

any suggestions welcomed!

each point in set has cover the intersection of cell in point-set's voronoi diagram , test-circle around origin.

to find radius, start computing voronoi diagram of point set. "close" voronoi diagram intersecting infinite edges target-circle. each point in set, check distance points of "closed" voronoi cell. maximum should solution.

it shouldn't matter cells closed arc instead of straight line test-circle until solution radius gets greater 1 (because "small" circles arc stronger). in case, have check furthest point cell center arc.


Comments

Post a Comment

Popular posts from this blog

objective c - Change font of selected text in UITextView -

-
can suggest me how change font of selected text in uitextview.i cannot use uiwebview since have edit text. have seen pages app.how possible in app. see formatting text within uilabel differently . since need editing, should @ javascript-based editors such ckeditor or tinymce . highly recommend wwdc 2011 video session 511: "rich text editing in safari on ios."
Read more

php - Accessing POST data in Facebook cavas app -

-
so i've got simple form in canvas / iframe facebook app, , i'm trying pass along values post. reading on s.o. , fb's latest docs, understand it, data send via post form can accessed on receiving end $_request object. i read on thread on s.o. in order post forms work need pass along input named "signed_request" value current signed_request (i have signed request working ok otherwise...all login , authentication stuff working fine). isnt mentioned anywhere in official fb docs. so problem comes in $_request object signed request, , bunch of other session stuff. form inputs found. the way can read them set method of form "request" isn't real form method. takes of inputs , sends them args in url. horrible. here's sample page canvas app form i'm using try debug (leaving out authentication stuff): <form enctype="application/x-www-form-urlencoded" method="post" target="_top" id="my_form" action=...
Read more

c# - Getting control value when switching a view as part of a multiview -

-
i have following code in aspx page: <asp:button id="display_button" runat="server" text="display" onclick="button1_click" /> &nbsp; <asp:button id="edit_button" runat="server" text="edit" onclick="button2_click" /> &nbsp; <asp:button id="save_button" runat="server" text="save" onclick="button3_click" visible="false" /> &nbsp; <asp:multiview id="multiview1" runat="server" activeviewindex="0"> <asp:view id="view1" runat="server"> <asp:formview id="view_program" runat="server"> <itemtemplate> <%# eval("status").tostring().trim() %> </itemtemplate> </asp:formview> </asp:view> <asp:view id="view2" runat="server"> ...
Read more