1
$\begingroup$

As shown in the figure, there are objects of arbitrary shapes placed on the surface of the sphere at arbitrary locations. The problem is to search the surface to locate these objects in most efficient manner.

Assumptions:

  • For simplicity, the sphere is half in size
  • The points(X,Y,Z) on the surface of the sphere are labelled as occcupied or not occupied

The naive approach to solve this problem is to scan the entire 3D surface of the sphere and find the occupied regions. But the complexity of this search would be whole area(2πr^2).

So, what would be the efficient approach to locate all the objects in terms of time complexity of the algorithm.

Any useful insights would be helpful. enter image description here

$\endgroup$
  • $\begingroup$ Are we talking about a physical sphere or virtual 3D sphere? If it is Physical how are you planning to scan it? $\endgroup$ – JJerome Jul 17 at 1:59
  • $\begingroup$ It is a virtual 3D sphere. Basically, it is just an arrangement of points in 3D space which forms this sphere. So, the points can be scanned. $\endgroup$ – ewaolx Jul 17 at 3:41
1
$\begingroup$

I suppose this is a question of what is "most efficient" and what are you actually doing? And how are you going about simulating it?

Are you looking for a mathematical proof of how to find all infinite points on the surface of a sphere? Do you have a specific amount of points to look for, like only 200 scattered around the surface and need to find the shortest path to look at each one to find a value such as O or NO ?

One is a mathematical thesis, the other is a path planning problem....

How are you scanning? Is this just a matter of querying 200 sensors with an MCU? This would be microseconds of calculation time simply querying a table of sensors giving back answers of true or false...

Going under several assumptions:

  1. You can Approximate your sphere with a polygonal mesh
  2. "Efficiency" means: The least amount of time looking for O or NO While physically scanning with some kind of rotating optical sensor...camera?
    • As such you need to be time and energy efficient.
  3. You only need to scan each point once.

I did this analysis using mathematica and igraphm (which you can get for free for a raspberry pi, but the methods are applicable to other softwares.

First generate an approximate sphere with 200 points, Create a DelaunayMesh Graph to generate vertices and paths between them.

pts = SpherePoints[200];
mesh = DelaunayMesh[pts];
path = IGDelaunayGraph[pts]

picture

Add weights to each edge between the vertexes based on euclidean distances

wg = IGDistanceWeighted[path]

Generate a Hamilton path between each vertex based on the distance weights, A Hamilton Cycle could alternatively be generated via FindHamiltonianCycle[]

way = FindHamiltonianPath[wg]

{28, 41, 54, 67, 80, 93, 106, 85, 72, 59, 46, 33, 20, 12, 25, 38, 51, 
64, 77, 90, 111, 98, 119, 132, 145, 158, 171, 184, 192, 197, 200, 
195, 187, 179, 166, 153, 140, 127, 114, 101, 122, 135, 148, 161, 174, 
182, 169, 156, 143, 130, 117, 96, 109, 88, 75, 62, 49, 36, 23, 15, 7, 
2, 5, 10, 18, 31, 44, 57, 70, 83, 104, 91, 112, 125, 138, 151, 164, 
177, 190, 198, 193, 185, 172, 159, 146, 133, 120, 99, 78, 65, 52, 39, 
26, 13, 21, 34, 47, 60, 73, 86, 107, 94, 115, 128, 141, 154, 167, 
180, 188, 175, 162, 149, 136, 123, 102, 81, 68, 55, 42, 29, 16, 8, 3, 
11, 24, 37, 50, 63, 76, 89, 110, 97, 118, 131, 144, 157, 170, 183, 
191, 196, 199, 194, 186, 178, 165, 152, 139, 126, 113, 92, 105, 84, 
71, 58, 45, 32, 19, 27, 40, 53, 66, 79, 100, 87, 74, 61, 48, 35, 22, 
14, 6, 1, 4, 9, 17, 30, 43, 56, 69, 82, 103, 124, 137, 150, 163, 176,
189, 181, 168, 155, 142, 129, 116, 95, 108, 121, 134, 147, 160, 173}

HighlightGraph[path, PathGraph[way3]]

final path

The final path between each point to scan....these points can now be programmed into your scanning device..the logic if something is at any one coordinate and it is O or NO and if the cycle should be broken off at this point, or just continue looking forever is up to the reader.

However this would be the method I would go about scanning things when it's required to find the shortest distance and least time.

I hope this is a method you're looking for...if this is a mathematical kind of question, I would suggest asking at maths.se

This of course can be scaled up to any number of points, depending on the "resolution" you're looking for...

Here's 1000 and the appropriate path to follow.

1000sds

$\endgroup$
  • $\begingroup$ Thanks for the detailed explanation! This is very close to what I am looking for except from the fact that, I am more concerned about the reducing the time it takes to query all the points. It sort of fine for me even if two adjacent points are not at the shortest distance, as I have their respective locations, but do not know, if they are occupied or not. $\endgroup$ – ewaolx Jul 20 at 19:52
  • $\begingroup$ If you update your question with some more infos...like how many points you're looking for or where they are on the sphere, the size of your sphere and the field of view of your ( I guess) camera, I may be able to design something better :) $\endgroup$ – morbo Jul 20 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.