# Which algorithm partitions the surface of a sphere in a meaningful way?

Edit: As suggested I have tried to describe my problem in a more formalistic way. Please bear with me, since neither english nor math are my native languages ;-) For the applied problem please see below.

Consider

• a sphere $a$ with a diameter of 1
• an "input point" $B$, located on the surface area of $a$
• a maximum orthodromic distance $c$ ($c \in \mathbb{R}$, $0 < c < \frac{\pi}{2}$)
• a set $D$ of points, randomly placed on the surface area of $a$
• a set $E$, subset of $D$, that contains all points for which the orthodromic distance to $B \le c$
• a set $F$ of spherical segments of $a$, obtained by cutting $a$ according to the algorithm $x$
• a number $y$ ($y \in \mathbb N$), specifying the maximum permissible number of points per spherical segment

Let

• the location of $B$ be random
• $c$ be random
• $D$ be a non-emtpy set
• $y$ be random

Which algorithm $x$ will minimize the number of spherical segments containing $E$? Which variables influence the optimal algorithm?

How about $y = 16000$ and $\left\vert{D}\right\vert = 2000000$?

Original question:

The following is a very practical question and might not be perfectly suited for math.stackexchange.com. If you feel that it is totally out of place here, please let me know. I am very thankful for pointers to the underlying theoretical problem as well.

As a just-for-fun computer science experiment I am writing a programme that retrieves content nodes adjacent to a geographic input position within a variable radius. The content nodes to be displayed have been assigned latitude/longitude values.

For simplicity, consider the positions of the nodes, the input position and the radius to be random.

The large number of content nodes suggested using multiple databases for the entries. As a simple first step, I created two databases. One for nodes with a $latitude < 0$ (southern hemisphere) and one for nodes with a $latitude > 0$ (northern hemisphere).

The strategy of dividing the latitudinal range by the number of databases available, and thus “slicing” the globe horizontally, at first seemed reasonable to me. However, in terms of performance, it is crucial to minimize the number of databases involved in retrieving the nodes. It feels to me as if this strategy is far from being optimally performant in consideration of the number of databases involved. Which algorithm produces an optimal result?

-
See if you can do this: leave the current content of the question in place, then add on, as an edit, a description of your problem entirely in mathematics terms. There seem to be a number of slightly different problems you could be asking about. – Will Jagy Jun 16 '13 at 20:31
The cs.stackexchange forum could be appropriate for this question too. When it comes to finding the "optimal" algorithm, there are a few aspects you might want to clarify: why is it important to keep the number of databases involved minimal (can't the queries be performed in parallel, thus actually improving the performance with more DBs?); is there anything you know about the distribution of the radius (e.g. are queries with small radius more likely than those with big one?); does it really need to be "partition" of the space or can the parts overlap; ... – Peter Košinár Jun 17 '13 at 7:49
... are the databases going to be updated often or are they (mostly or completely) read-only during the querying process?; are you looking for all nodes within the specified radius from the given one, or just the (few) nearest ones? All of this (and certainly more) can have important effect on the structure and performance of the "optimal" algorithm. – Peter Košinár Jun 17 '13 at 7:52
@PeterKošinár The total number of databases is relevant. Practically speaking, all databases should be operating near full capacity. The databases involved in one query should be minimal. The radius in the implementation will be somewhere around 50m and 5km. A radius around 250m is most likely. The parts could overlap. The databases will be ~98% read ~2% write. I am looking for all nodes in the radius in no particular order. – mritz_p Jun 17 '13 at 13:07
Since the parts are allowed to overlap, your idea with two hemispheres can be extended to guarantee that only access to a single database will be needed -- just expand the hemispheres a bit, so that the 10km (= double the maximum permitted radius) wide strip around equator will be covered by both. The same approach can be used if you split the database into more parts; just extend the boundaries of each part "a bit" (maximum permitted/expected radius of the query) – Peter Košinár Jun 17 '13 at 13:33