I have already been thinking about the problem of detection in aurora (and other systems like it) before I saw this thread. In general, one first need to realise that detections are a type of colition detection, and can make use of many of the relevant algorithms for dealing with this.
My suggestion is to try to predict when the next change of detection status could occure. There are many ways to go about this, so I will just present the most simple one, and leave more powerfull and complex versions until another time. The general idea is to come up with some prediction of when 2 objects (either detector or detectable) can either lose sensor contact or gain sensor contact. In general this can only happen when 1 of 2 things occure: Either sensors/emission is turned on or off by some event (like activating active sensors, changing speed, jumps between systems, damaging components and such) or an object enters or leaves the detection range of a sensor. Since the change events can be handled when they happen (and as such does not need to be handled by the sensor phase), we just need to predict when objects enter or leave the detection range.
In general we can group all objects into 3 catagories of movement: stationary objects (such as jump points and stranded ships), orbiting objects, and freely moving objects. For each set of object types, we simply need to assign some prediction of when they could happen to detect each other. The most conservative and simple option would simply be to assume that any 2 objects will be heading strait toward each other (ignoring that they are probably following another trajectory) and by using their current speed calculate when they will get within the range for each other. If we are tracking disengagement, we would instead assume they were moving away frome each other. For stationary objects, their speed will be 0, while orbitig objects could be described as bands of detection, though this can easily get quite complicated with nested orbits or orbit to orbit detection. Anyway, since we can always atleast use the "move dirrectly toward or away" model, we can always come up with an estimate which will never be too late, and will work for all types of movement.
When we have such detection times, we can simply put them into an ordered queue (such as a min-heap), and simply only check for detection when we arrive at the time of the event at the top of the queue. There are 2 speed ups form this. First off, events could be many many subpulses away from each other, and we would not need to do any sensor checks in those phases. Second off, it would only really be necessary to do a single sensor check when an event fires off, since it was only really relevant with one pair of sensor/detectable. Ofcause one could do a full check and reset update the positions in the queue, if there is some reason to do it that way instead. This could potentially significantly reduce the amount of sensor checks needed to be done, since it will only try it when it is relevant. Since it is possible to ensure detection at the same accuracy as before with the conservative models metioned above, it would not even have to be limited to NPR vs NPR detection, though one could definitely get away with using some less conservative models, which would generate fewer events but risk being slightly inaccurate.
Concerning the civiliance, I would personally be happy if there was an option to disable them. I would rather have to do most of the jobs they do myself. While they do add something to the game, their potential high performance cost makes them a decent target for performances optimization (just as grafic heavy games often have options which makes the game much more ugly but significantly increases performance).
There are a lot of things that could be potentially be done to the NPR movements and civilian trade runs, which could improve performance. But those would depend on what type of system is already implemented, and they would only really be improvements if they are upgrading from a slower system.
