Efficient sphere surface area search

Question

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.

Answer 1

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]

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]]

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.