wrhall / computational_geometry Goto Github PK

Write some code to use to benchmark (speed test) two identical functions.

Just a template file would be fine, but it could be improved to something beautiful and metaprogram-y.

1. Expanding interval the least (or weighing it down as heavily as possible).
2. Pick the next element to be closest to the mean of the unused numbers (besides itself).
3. Anything else batshit?

Improve the speed of find_interval: current suggestion -- use a dynamic programming idea (bellman-ford idea) to save all possible sub intervals. Then a new interval (adding one more number) is just going to be the old interval with a new upper or lower bound (or the same upper and lower bound).

The max c_i occurs immediately before or after the min c_i.

1. There is no set of 3 that doesn't start with the middle.
2. The apx4 is a 2-apx. (pick x_i to make c_i as close to c_n as possible)
3. The first element is always an element an either side of c_n in the sorted array.
   -- Stronger -- It is always the closest that is in the final interval (This might be wrong)

1. Claim: Every set will have a possible starting point just to the left or right of the final center of mass (left or right meaning .prev or .next, ie sorted left or right)
   [stronger: closest to the final center of mass]**
2. Claim (unproven): If we can talk in terms of going up and then down and then up and then down to get a Cradle, then there will not be a list of numbers such that we skip one going up and then skip one going down.
   Idea / Justification: If this happens, then you could take the two inner numbers and add them first (which would have an impact at least as small as before)
3. New claim / algorithm idea: I think you could maybe make a greedy alg that pairs up items. So assume claim 2 holds
   Then, consider the next 2 points to add. Select the two points such that they minimize the interval growth.
   (we think that one of the points would be the closest [on its side] to c_n)
   (Break ties by selecting the innermost points -- closest to c_n on either side)

False claims:
2. Claim: If c_i < c_{i+1}, then c_{i+1} > c_{i+2}
alt claim: Given c_n, opposite parity c_i will be on opposite sides of c_n (odds on one side, even on the other).
false

\5. Claim (unproven): If exactly 2 opt solutions, they are cradle complements.
False, can have opts where values are switched

Heuristic ideas:

1. Append the next number that increases the current range the least -- branch on ties.

\2. Heuristic idea: Branch on 3-7 next closest options in opposite direction (using Claim 2).

NP complete proof?

Intervals that are the unique optimal:
[-1, -9, 7, -18, 20, -20] <-- Cradle (aka perfect cradle)
[5, 3, 9, -1, 13, 2]
[0, 2, -4, 5, -7, 3] <-- Alternating (but not a cradle)
[4, 8, -6, 13, -7, 20, -20] <-- Cradle

Fact: The best interval does not necessarily contain the best subintervals.
ie: [9, 2, 13, -1] --> subinterval [2, -1, 13]

Add tests to the functions -- make sure the functions behave how we expect them to.

Invariant for God Probem:

1. Current C_i is between [a, b] (unless there's no solution)
2. There is no universe in which adding an extreme point is the best C_i.