Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>This problem is similar to the classical problem of finding the closest pair in a set of points. You can adapt the worst-case <strong>O(n log n)</strong> algorithms that solve the closest-pair problem to solve this one.</p> <p>The specific problem was featured in Google's Code Jam competition. Here is a resume of the analysis:</p> <blockquote> <p>The number of points can be pretty large so we need an efficient algorithm. We can solve the problem in <strong>O(n log n)</strong> time using <em>divide and conquer</em>. We will split the set of points by a vertical line into two sets of equal size. There are now three cases for the minimum-perimeter triangle: its three points can either be entirely in the left set, entirely in the right set, or it can use points from each half.</p> </blockquote> <p>Further:</p> <blockquote> <p>"To find the minimum perimeter for the third case (if it is less than p)":</p> </blockquote> <ol> <li>We select the points that are within a distance of p/2 from the vertical separation line.</li> <li>Then we iterate through those points from top to bottom, and maintain a list of all the points in a box of size p x p/2, with the bottom edge of the box at the most recently considered point.</li> <li>As we add each point to the box, we compute the perimeter of all triangles using that point and each pair of points in the box. (We could exclude triangles entirely to the left or right of the dividing line, since those have already been considered.)</li> </ol> <blockquote> <p>We can prove that the number of points in the box is at most 16, so we only need to consider at most a small constant number of triangles for each point.</p> </blockquote> <p>It seams to me you could even adapt the method to work in the |AB|²+|AC|²+|BC|² case.</p>
    singulars
    1. This table or related slice is empty.
    1. POClosest group of 3 points
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USThomas Ahle
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COCan you give more details?
      singulars
      1. PO
      1. USfinnw
    2. COIf you read the 2d divide and conquer closest point algorithm, you should notice that it easily works for three points as well. Wikipedia then describes how it works on nlogn for any number of dimensions.
      singulars
      1. PO
      1. USThomas Ahle
    3. COI do not see how it "easily" works for three points. The step where you look for 2 closer points on opposite sides of the dividing plane does not (trivially) generalise to 3 points.
      singulars
      1. PO
      1. USfinnw
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload