This page helps generate examples where Ruppert's refinement algorithm for quality 2D Delaunay mesh generation runs in time quadratic in the size of the output mesh as described by Jernej Barbič and Gary Miller in "A Quadratic Running Time Example for Ruppert's Refinement Algorithm." The output example is in .poly format that can be used directly with triangulation tools like Triangle.

Below, n and α are as defined in the paper i.e., (n + 4) points are generated inside the box such that α is the minimum allowed angle to be required of the triangulation algorithm. The scale is primarily introduced to help with the display.

Last updated: Oct 30th, 2013

Your browser does not support the HTML5 canvas tag.