Differentiable Range-Partition Entropy for Entropy-Sensitive Geometric Algorithms

Range-partition entropy is a structural complexity measure used in entropy-sensitive computational geometry. We introduce Differentiable Entropy Regularization (DER), a gradient-optimizable surrogate for the entropy of learned geometric partitions. The paper makes three main contributions. First, we separate the normalized entropy optimized by DER, denoted Hnorm(S), from the runtime-scaled entropy Hwork(S) = n · H_norm(S) that appears in algorithmic work bounds. Second, for a fixed margin-separated halfspace arrangement, we prove a self-contained soft-to-hard approximation theorem: the soft halfspace-cell entropy converges to the corresponding hard sign-pattern entropy at a rate controlled by margin, temperature, and the number of separators. A connection to optimal range-partition entropy holds when the fixed partition is admissible for the geometric problem and near-optimal in the admissible partition class. Third, we evaluate DER as learned geometric preprocessing for SciPy/Qhull-based convex-hull and Delaunay pipelines. On the evaluated 2D tasks, DER gives up to 4×–5× solver-side speedups and smaller end-to-end gains after preprocessing, with convex-hull area error below 0.2%. We also include a secondary transfer study in ViT-style attention, where the same regularizer induces structured sparsity and improves empirical efficiency. The central contribution is not the entropy formula alone, which resembles soft clustering, but the range-aware differentiable construction, the explicit approximation analysis, and the geometry-first training pipeline.