Page 1 of 1

Interdictor maths

Posted: Sat Mar 23, 2019 1:06 pm
by Aightaight
I was listening to my audiobook* of the Subjugation series for the third time when the following passage from Unification Chapter 7 caught my attention:
they were aiming at only three layers [of interdiction], which would require 43 interdictors laid out in a specific pattern to create a total barrier of three light years in any direction from the edge of interdicted space to Karis. If he wanted four light years, that number skyrocketed to 253
[* created with the free text-to-speech program "Balabolka", using the Microsoft Hazel voice, Pitch=-10, Rate=2]

In the nerdy part of my brain, the following two questions arose:
- Are the 43 and 253 values accurate?
- What configuration should be used to minimize the number of interdictors required to cover a given volume?

I thought the answers to these questions would be fairly easy to find with a quick google search, but boy was I wrong.

You see, while there's plenty of information available about the best way to pack spheres into a given volume (known as the "sphere packing problem"), even the best packings utilizing uniform spheres leave over a quarter of the volume uncovered.

If we don't want to leave any gaps within our interdiction field, then we're really after a solution to the "3 dimensional ball covering problem". And there's a lot less information available on the web about covering problems than there is for packing problems. Finding an optimal covering is a non-trivial task, even in two dimensions (eg https://www2.stetson.edu/~efriedma/circovcir/), and the three dimensional case is even more difficult.

For anyone interested, here's what I discovered after looking into this topic over the course of several hours:

Firstly, I was fortunate to find a webpage which provides the configuration needed to generate a two light year radius interdiction field with the fewest possible interdictors: https://mathoverflow.net/questions/9800 ... the-radius. (You'll need to scale everything on that page up by a factor of 2, since the interdictors have a 1 LY radius, rather than the 1/2 unit used on the page).

Basically, the most optimal configuration requires 1 interdictor at the center, surrounded by a second shell of 20 interdictors placed sqrt(3) LYs from the origin, for a total of 21 interdictors.

Unfortunately, I couldn't find a description of how to optimally add on more shells to expand the field. I highly doubt 43 interdictors would be sufficient to generate a 3-shell 3 LY radius field, though, as a minimum of 21 interdictors is already required to generate a 2-shell 2 LY radius field. It might be possible to get close to 3 LY with a 2-shell set-up though, for example by using an inner shell at the vertexes of an icosahedron, and an outer shell a sufficient distance away from the inner shell to cover the rest of the volume. That's entirely my own speculation though, and I'm not really up to the task of finding out for sure.

Secondly, while my maths & google-fu skills are far from sufficient to find the minimum number of interdictors required to cover larger spherical volumes, I did find a less-than optimal but more accessible solution that can be scaled up to provide gap-free interdictor coverage for any rectangular volume.

Simply put, spheres don't tessellate, but cubes do. The largest cube that can be inscribed inside a sphere of radius 1 LY has edges of length 2/sqrt(3) LY, so we can pretend that each interdictor will cover a cube of side length 1.1547 LY, then ignore the bits of the sphere that project out beyond the surface of the cube.

Thus all we need to do is stack our cubes together to cover the volume we want to interdict. A 4 x 4 x 4 stack of interdictors will cover a cubic region of space 4 x 1.1547 LY = 4.6 LY across, which is sufficient to enclose a 2.3 LY radius sphere. A 5 x 5 x 5 stack will cover a 5.7 LY cube (enclosing a 2.85 LY radius sphere), a 6 x 6 x 6 stack covers a 6.9 LY cube (enclosing a 3.45 LY radius sphere), and a 7 x 7 x 7 stack covers an 8.08 LY cube (enclosing a 4.04 LY radius sphere).

Thus, even with our sub-optimal cube-stacking arrangement, 343 interdictors will easily cover a 4 LY radius sphere (actually, we can eliminate 7 interdictors at each of the 8 corners of the cube while still enclosing the 4 LY sphere, thus requiring only 343 - 56 = 287 interdictors). It is therefore plausible that the 253 interdictors mentioned in the story would be more than sufficient to cover a 4 LY radius sphere if we used a more optimal spherical shell stacking configuration.

* * *

Anyway, fun though it was to look into this topic, I think I'll leave the rest of the maths to Myli and Cybi. Or anyone else who feels their maths skills are up to the task.

Best of luck if you decide to take on the challenge!

Re: Interdictor maths

Posted: Mon Mar 25, 2019 5:43 am
by GBLW
Just one question: if you use the cubic method, what do you do about the gaps, because I can't "see" how they would work out to give a full overlap?

PS: I'm getting fairly old and not a major math nut, just a long retired engineer, so a simple answer may have eluded me.

Re: Interdictor maths

Posted: Mon Mar 25, 2019 7:59 am
by kyli
I think multiple Interdiction layers work by continuing the first Interdiction field, not by having hundreds of different spherical interdiction fields, creating one giant field instead of a bunch of smaller ones. Also an interdictor is creates a field 1 LY in radius or 2 LY's in diameter. Maybe the extra layers only need that many because its only continuing an existing field in one direction.

PS - I suck at math so I mostly skimmed your message and ain't even gonna start trying to figure it out.

Re: Interdictor maths

Posted: Fri Mar 29, 2019 4:07 am
by Greymist
GBLW wrote: Mon Mar 25, 2019 5:43 am Just one question: if you use the cubic method, what do you do about the gaps, because I can't "see" how they would work out to give a full overlap?

PS: I'm getting fairly old and not a major math nut, just a long retired engineer, so a simple answer may have eluded me.
Aightaight was taking a sphere of 1LY radius (2LY diameter) and then taking the largest cube which would fit *inside* the sphere, in effect trimming off six sections of the sphere to make a cube with side lengths of 1.1547LY (I think the maths is wrong here, it should be actually 1.41, but anyway)

This way there is lots of overlap, and no gaps.

I might look into this more when I'm sitting at a laptop instead of my phone in a coffee shop, but I believe you can "tessellate" (or really space fill) with two different types of sphereoid 3D polygons and that would waste less area than the cube approach

Re: Interdictor maths

Posted: Fri Mar 29, 2019 8:28 am
by GBLW
Gotcha, Thank You! Because as I saw it by making outer dimensions of the cubes that large, they left spaces between the layers (even in a two dimensional layout), which I didn't think would be 'safe' as a 'barrier.'
But, as I said I'm not a math nut - I just have this odd sense that can "almost see/feel" in three dimensions. When something isn't quite right it 'niggles' at me (It's a 'sense' that I used for years, because it often helped in doing designs of 3D objects on paper before taking them to the machine shop.)

Re: Interdictor maths

Posted: Sat Apr 06, 2019 3:53 am
by lapland
I believe Fel went over the interdictor math in a post years ago when he first incorporated them into his story. He discribed the large numbers that would be require for a true three layer system, and explained how he was going to use a two layer system to protect Earth. It might have been modified as a sudo third layer by placing them at the center of each gap to close but I’m not certain what he said all these years later.

Re: Interdictor maths

Posted: Sat Apr 13, 2019 3:13 am
by SoronelHaetir
Remember in comparison with the packing problems interdictors can overlap (normal physical spheres, of course, can not). And you would need that overlap to completely 'fill' the area to be interdicted because any uncovered area the enemy could jump into hyperspace or whatever other higher-brane travel method is being used. So try finding a solution to minimum number of spheres needed to occupy the same area as a single larger sphere rather than the packing approach. The outer 'surface' may still look like a berry with lots of bulges but the interior will be occupied.

Re: Interdictor maths

Posted: Sat Apr 13, 2019 11:56 am
by kyli
Here is a quote of Fel explaining layered interdiction fields, found here.... viewtopic.php?f=12&t=2360#p31700
Fel wrote:The full description is that layered interdiction fields intersect, they don't touch edges, and each additional layer of interdiction only uses half its interdiction field to extend the field out further. That's why there's only a three light year interdiction field around Karis instead of a FIVE light year field. To maintain maximum coverage and prevent ships from maneuvering along the edges of the interdiction fields, the second and third layers of the multi-interdiction field around the system only extend it out ONE light year, instead of two.

Remember, the interdictor has a interdiction field of a one light year RADIUS, not DIAMETER.

The interdictors are arrayed so that the next layer of interdictors sits right at the edge of the interior layer's interdiction effect, extending the interdiction out one more light year. This array creates an overal interdiction field that generates its field in a uniform direction, i.e., the entire interdiction field has a uniform waveform, and thus the entire field is "outbound" all the way to the edge. 

By layering the interdictors in this manner, it creates an overall complete sphere of interdiction 3 light years in radius rather than am irregular rumple-bordered effect that might be 5 years in radius at one point and 1.6 years at another. The objective of the interdiction field is to prevent maximum difficulty for those jumping IN, they don't much care about the ability of ships already in to jump OUT.