If the graph is planar and you have it's embedding, then you can do
better than O(N), at least on a random graph. Otherwise this has to be
impossible because the graph gives you no information, and you must
look at each vertex.
On Jan 5, 1:17 pm, dabbcomputers dabbcomput...@gmail.com wrote:
you
On Jan 5, 4:17 am, dabbcomputers dabbcomput...@gmail.com wrote:
you are given with N points on graph. and a point A on graph and range
R you have to find the points that lies within the radius of R from
point A. with complexity less than O(N).
Why does it have to be done with less complexity
@Gene: I didn't understand on what you termed as embedding Can you
provide more insights on this?
@dabbcomputers: also, listing set of points (not just one) isn't going to
be a better than O(n) solution.
for eg: a value of R that eliminates only half the points outside the
circle.
--
You
An embedding is the information that says how the graph is laid out
with no edges crossing. As a data structure, it can be given in
various ways. The simplest is for adjacency lists of each vertex to
be given in sorted order clockwise or anti-clockwise.
On Jan 7, 5:10 pm, sravanreddy001
Assuming that the N points on the graph are represented in the form of
(x,y) i.e. cartesian coordinates..
Then say, A = ( a1, a2);
The equation of the circle centered at A would be
(x - a1)^2 + (y-a2)^2 = R^2...
Now, to find the points that lie within the range R, u need to check
the following
@ all
Ignore my previous post
On Jan 5, 5:58 pm, Lucifer sourabhd2...@gmail.com wrote:
Assuming that the N points on the graph are represented in the form of
(x,y) i.e. cartesian coordinates..
Then say, A = ( a1, a2);
The equation of the circle centered at A would be
(x - a1)^2 +
Cut out the circle from the graph. The points on the cut-out circle
are the answer.
Don
On Jan 5, 6:17 am, dabbcomputers dabbcomput...@gmail.com wrote:
you are given with N points on graph. and a point A on graph and range
R you have to find the points that lies within the radius of R from
i also think so data must be represent in some special form i heard
about K-D trees but not yet studied about it
On Fri, Jan 6, 2012 at 12:26 PM, Lucifer sourabhd2...@gmail.com wrote:
@all..
To decide which points are within the range R, we need to look a each
point..Hence the
the reason i asked you about problem link is because the solution to your
problem depends on the way you want to use it...
1. if each time there are new N points and radius R, and only one query
for it...then it just can't be O(n)
2. if N points are fixed and there are like 1+ queries then
@shady the N is same we just have to query the data again and again
On Fri, Jan 6, 2012 at 12:47 PM, shady sinv...@gmail.com wrote:
the reason i asked you about problem link is because the solution to your
problem depends on the way you want to use it...
1. if each time there are new N
10 matches
Mail list logo
