S.O.S. Mathematics CyberBoard

Hi all,
I have the following Algorithm which I simply want describe in words to make it simpler to understand. My goal is to double check if I am right about its complexity.

I have a grid of lines (n*n). Each line represents a linked list which stores a node and the content of that node is the length of the line. Say I want to cover these lines by circles randomly placed on them. In other words, I want to place randomly a circle which covers a line(s). Based on the intersection of this circle (knowing its position and the intersected lines positions with the circle) we go to each line and then modify the content of the node by reducing its value as if the line became shorter (covered). We stop once all the lines have been covered by the circles (i.e., all the nodes in the linked lists have value of zeros). Now if the word "randomly" confuse you we can just assume for now that after a period of time the grid will be fully covered (We talk later about this).

The way that I think that this algorithm should be implemented is in linear time since I am dealing with an array of linked lists and based on the known position of a node and the positions of the intersected lines, we can easily know which lines to modify their linked lists.
So I would say that this algorithm has a complexity of O(n). What do you think?

Your question and algorithm description are rather unclear to me.

How many lines are there? Is there one linked list in each line or N linked lists in each line? How many linked lists do you have in total? How many nodes does each linked list have? What do you mean by "circle"? A circle is a set of points, but you're not talking about points here you're talking about nodes, so please define your context.

Thanks!

Thank you dionyziz for the follow-up.

>>>How many lines are there?
It depends on the distances between any pair of lines, so say that for 9*9 (n*n), with spacing between any pair of lines is equal to 3m (N). We have the following

|------------|-------------|
|!!!!!!!!!!!!|!!!!!!!!!!!!!|
|------------|-------------|
|!!!!!!!!!!!!|!!!!!!!!!!!!!|
|------------|-------------|

(3 horizantal lines and 3 vertical lines)

By the way n and N can be arbitrary. BTW "!" only means a space where as | and - form lines.

>>>Is there one linked list in each line or N linked lists in each line?
For Each line, there is one linked list.

>>>How many linked lists do you have in total?
In the above example it is 9 linked lists.

>>>How many nodes does each linked list have? What do you mean by "circle"? A circle is a set of points, but you're not talking about points here you're talking about nodes, so please define your context.
Each time I randomily place a circle (i.e., sensor node such that it has a sensing circle) one at a time until all these lines are fully covered by some sensing circles.
so each time I do this, I might end up with different set of sensor nodes on the gird. Regarding the sensing circle, I am checking if the circle intersects one or more of the lines. when I am talking about a node (without mentioning the word sensor next to it), I mean a node in the linked list.

One more thing the sensing circle as a raduis R and also it is arbitrary.

Thank you.

I'd think it'd be important to know for certain what role the circle (sensor) plays in your analysis. The algorithm can be much more efficient and simple if you can use little sensor radii towards the end.

However, if you're trying to do something with the sensors, like finding the minimum number of sensors required, it could get more complicated.

The algorithm seems like it will run in , where is the number of entries that you must check inside each sensor radius. If you don't need to worry about the circles at all, it can run in :D

Otherwise, you may want to consider getting a little more complicated...

I hope that this helps

Thank you Generator for the follow-up.
When you said that it can be O(n) or O(c*n), do you refer n to the number of sensor nodes? and for c do you refer it to the number of lines intersecting the sensing circle?

Since like I mentioned before n*n but from what you posted, I understood it as number of sensor nodes. Just want to make sure about something, that each line might have one more sensor covering it, say 2, to explain it more, suppose that the first sensing circle hit the line at a position where there are still some remaining uncovered parts of this line, so the second sensor node came and covers these parts.

Thanks in advance

This seems like a fairly complicated problem...
We could temporarily define the following variables:

refers to the number of lines across the grid
refers to the TOTAL amount of positions in the grid
refers to the amount of circles or sensors in the grid
refers to the radius of a sensor

So going through the grid and covering all positions requires or covering checks, at the mininum. In the worst case, this could mean compares for each "covering check".

However, going through the grid also requires sensor placements which each require checks where refers to the geometric average of all sensor radii. This gives us approximately .

So far, we're still left with two running times and an initial estimate of:


I believe that we still should know more about the algorithm. Is this definitely the algorithm that you want to stick with? I ask this because we should know exactly how the sensor placement works to get a very exact estimate of the running time. The sensor placement could really change this.