Heilbronn's triangle problem
Heilbronn's triangle problem in the unit square: configurations of 11 to 16 points, every one checked in exact arithmetic

| 1 | #!/usr/bin/env python3 |
| 2 | """Reproduce Comellas--Yebra (2002), page 7, using only decimal arithmetic. |
| 3 | |
| 4 | Source: https://doi.org/10.37236/1623 |
| 5 | Usage: python3 generate.py [--digits 60] > n12.txt |
| 6 | No search or random seed: the points are the published construction. |
| 7 | """ |
| 8 | import argparse |
| 9 | from decimal import Decimal, localcontext |
| 10 | |
| 11 | |
| 12 | def coordinates(digits): |
| 13 | with localcontext() as context: |
| 14 | context.prec = digits + 40 |
| 15 | a = Decimal(27) + 3 * Decimal(57).sqrt() |
| 16 | # t is the positive cube root of 27 + 3 sqrt(57). |
| 17 | t = Decimal(4) |
| 18 | tolerance = Decimal(10) ** -(context.prec - 8) |
| 19 | for _ in range(200): |
| 20 | next_t = (2 * t + a / (t * t)) / 3 |
| 21 | if abs(next_t - t) < tolerance: |
| 22 | t = next_t |
| 23 | break |
| 24 | t = next_t |
| 25 | else: |
| 26 | raise ArithmeticError("cube-root iteration did not converge") |
| 27 | x = 1 - (t * t + 6) / (6 * t) |
| 28 | y = 2 * x * x - 3 * x + Decimal("0.5") |
| 29 | zero, half, one = Decimal(0), Decimal("0.5"), Decimal(1) |
| 30 | points = [ |
| 31 | (x, zero), (one - x, zero), (zero, x), (one, x), |
| 32 | (half, y), (y, half), (one - y, half), (half, one - y), |
| 33 | (zero, one - x), (one, one - x), (x, one), (one - x, one), |
| 34 | ] |
| 35 | return "".join(f"{px:.{digits}f} {py:.{digits}f}\n" for px, py in points) |
| 36 | |
| 37 | |
| 38 | if __name__ == "__main__": |
| 39 | parser = argparse.ArgumentParser(description=__doc__) |
| 40 | parser.add_argument("--digits", type=int, default=60, |
| 41 | help="digits after the decimal point (default: 60)") |
| 42 | args = parser.parse_args() |
| 43 | if not 1 <= args.digits <= 1000: |
| 44 | parser.error("--digits must be between 1 and 1000") |
| 45 | print(coordinates(args.digits), end="") |