Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
We prove the existence of an algorithm A for computing 2D or 3D convex hulls that is optimal for every point set in the following sense: for every sequence σ of n points and for every algorithm A ′ in a certain class A , the running time of A on input σ is at most a constant factor times the running time of A ′ on the worst possible permutation of σ for A ′. In fact, we can establish a stronger property: for every sequence σ of points and every algorithm A ′, the running time of A on σ is at most a constant factor times the average running time of A ′ over all permutations of σ. We call algorithms satisfying these properties instance optimal in the order-oblivious and random-order setting. Such instance-optimal algorithms simultaneously subsume output-sensitive algorithms and distribution-dependent average-case algorithms, and all algorithms that do not take advantage of the order of the input or that assume the input are given in a random order. The class A under consideration consists of all algorithms in a decision tree model where the tests involve only multilinear functions with a constant number of arguments. To establish an instance-specific lower bound, we deviate from traditional Ben-Or-style proofs and adopt a new adversary argument. For 2D convex hulls, we prove that a version of the well-known algorithm by Kirkpatrick and Seidel [1986] or Chan, Snoeyink, and Yap [1995] already attains this lower bound. For 3D convex hulls, we propose a new algorithm. We further obtain instance-optimal results for a few other standard problems in computational geometry, such as maxima in 2D and 3D, orthogonal line segment intersection in 2D, finding bichromatic L ∞ -close pairs in 2D, offline orthogonal range searching in 2D, offline dominance reporting in 2D and 3D, offline half-space range reporting in 2D and 3D, and offline point location in 2D. Our framework also reveals a connection to distribution-sensitive data structures and yields new results as a byproduct, for example, on online orthogonal range searching in 2D and online half-space range reporting in 2D and 3D.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.000 | 0.001 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.000 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.001 |
| Open science | 0.005 | 0.001 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it