bmershon

A convex combination of three vectors in the plane allows us to represent any vector in the convex hull determined by those three vectors.

bmershon

An implementation of shellsort with a visualization based off of Mike Bostock's Quicksort animation.

Red lines indicate every hth index as the algorithm performs insertion sort for h independent interleaved sorted subsequences.

bmershon

An improvement upon a previous presentation of Shellsort. Here, each color indicates the elements which may be swapped during a given iteration of Shellsort.

The number of colors converges to 1 by following a sequence generated by the following code:

  while (h < N/3) h = 3*h + 1;

  ...
  
 //in the main loop

bmershon

Compare this naive implementation of quicksort to Dijkstra's implementation of 3-way partitioning.

bmershon

The Dutch national flag problem exposes an example of an input for which quicksort performs poorly. When there are many duplicates in the array to be sorted, it will often be the case that unecessary function calls to the recursive sort() method will be made on subarrays that already contain elements that are all equal.

The three bars of the Dutch National Flag hint towards another way of thinking about partitioning an unsorted array: move elements around such that elements we have all the elements less than pivot element, followed by all elements equal to the pivot element, and then all elements greater than the pivot element. In the case of an unsorted array of just three different values, say, red, white, and blue, we can imagine that sorting these shuffled values around would lead to a final structure much like the Dutch National Flag.

This implementation of quicksort uses Dijkstra's clever partitioning algorithm to expand regions of v

bmershon

Any polygon can be decomposed into a finite (though possibly large) number of polygons that can be rearranged through rotations and translations to form another polygon of equal area. This is known as equidecomposition.

The first step in one well-known algorithm for accomplishing this involves decomposing a triangle into a square.

In order to decompose a triangle into another triangle of equal area, it is necessary to intersect collections of polygons contained in a square common to both triangles.

See d3-equidecompose.

bmershon

license: gpl-3.0

bmershon

license: gpl-3.0
border: yes

bmershon

The Sutherland-Hodgman clipping algorithm is used here to compute the intersection of two Delaunay triangulations with one another. Sutherland-Hodgman implementation by Joy Patel.

This algorithm can be used to intersect the decomposition of one triangle with a decomposition coming from another triangle of equal area.

For a decomposition of two triangles of equal area that uses Sutherland-Hodgman clipping, see this example.

See d3-equidecompose.

bmershon

border: yes
license: gpl-3.0
height: 5500
width: 1400
scrolling: yes