this is for holding javascript data
Xavier Holt added We_repeat_this_for_every__.md
almost 8 years ago
Commit id: 44b951b6d07829338b7699f23b24f9dbff53103d
deletions | additions
diff --git a/We_repeat_this_for_every__.md b/We_repeat_this_for_every__.md
new file mode 100644
index 0000000..3066d39
--- /dev/null
+++ b/We_repeat_this_for_every__.md
...
We repeat this for every line. We do a constant amount of work at every intersection, giving us a \(O(n^2)\) time algorithm for labeling every edge.
From here, we traverse through every face. Each face is convex, as such the convex shape is either above or below every edge-line. Hence when we arrive at a face, we take just one of its edges:
* If we have an edge which is above our face, then any point in the face is above the same number of lines as our edge. This follows from the fact that there can be no other line in-between this top edge and our point. As such we can annotate our face as above the same number of lines as our edge.
* If we have an edge below our convex hull, then any element in the hull will be above all of the lines this edge is above. It will also be above the line itself. As such, we annotate our face with one more than the number of lines our edge is above.
To find if an edge is above or below a convex hull, we simply take any point within the hull and see if the vertical intersection point is above or below our point.
This is another \(O(n^2)\) traversal with constant work done at each point. As such our total annotation time is \(O(n^2)\).
