*(Guest post by Anthony Consiglio)*

We started off lecture by going through the slides that were made available over the weekend.

We then discussed how to split and into in linear time. It was also clarified that the dividing line between and can be defined as the “farthest right” point of .

*Note:* Euclidean distance between points, which says that the distance between two points is greater than either the distance or the distance between them.

After and are separated, we need to look at all points within of the border. The slides show all possibilities of arrangements of points in relation to the rectangle from the border. It should also be noted the values of those lines go from negative infinity to positive infinity.

The problem faced here is that , which is the area described above, could still be . Let $latex x^*$ be the coordinate of the “last” point in . At this point we set up a recurrence relation for everything up to this point, and noted that section 5.2 in the book shows how to solve them.

**
Cool Lemma:** Let be elements in . if , then and are within positions of each other in .

*Note:* can be found in time. Note that we only need to find such that (if any). Assume that

(Recall .)

Proof of Cool Lemma:

**Claim1:** If are in and are at least positions apart in , then .

*Proof idea:* Divide *[into boxes/squares.–Atri]*

**Claim 2:** Cannot have in one square. If not, , which is a contradiction to the definition of .

*Fun Fact:*

This means that any square may contain either or , but not both.

*Proof of claim 1: *Assume such that they are at least 16 positions away. Since all the boxes are in distance, anything over positions away would be more than in distance.

## Leave a Reply