gpt 6 astra ultra attempt on CS-94

Research-attempt provenance

Definitions and mathematical statement

A polyhedral subdivision of three-dimensional space is a finite face-to-face complex whose three-dimensional cells cover a prescribed polyhedral domain (with an exterior cell if needed). Its faces, edges, vertices, and incidence relations are given explicitly. Let $n$ denote its total boundary-description complexity; in a triangulated description this is the number of constant-size boundary faces up to constant factors.

A point-location query supplies $q\in\mathbb R^3$ and asks which cell contains it. Boundary points may be handled by a fixed deterministic tie rule, or the query can report an incident cell. The central question is whether every such subdivision admits a data structure with \[ O(n)\text{ storage},\qquad O(\log n)\text{ worst-case query time}. \] Preprocessing must construct the structure from the subdivision; its cost should be stated separately. The bounds refer to a standard real-arithmetic/pointer model with constant-size geometric records.

Counting each polygonal face as one unit regardless of an unbounded number of vertices would conceal input complexity, so that convention is not used. The requested simultaneous space and query bounds are stronger than obtaining either bound alone with an unrestricted cost for the other.

Short English statement

Can arbitrary three-dimensional polyhedral subdivisions support logarithmic-time point location using only space proportional to their input complexity?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 5500013 (AMR-054-0013), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problems Project - Computational Geometry, Problem 13. Original source indexed by AMR-054-0013. https://topp.openproblem.net/p13.

Literature and context check

TOPP Problem 13 was consulted for the simultaneous space/query target. The page records historical tradeoffs, not a proof that a particular elementary hierarchy achieves both desired bounds. The following construction audits that hierarchy without claiming an impossibility theorem for all data structures.

Research attempt: Testing balanced spatial subdivision as a point-location route

Consider the unit cube subdivided into $m$ closed horizontal slabs \[ C_j=[0,1]^2\times[(j-1)/m,j/m],\qquad 1\le j\le m. \] Their full face/edge/vertex description has complexity $\Theta(m)$; neighboring slabs meet face-to-face, and side faces are subdivided at the same levels. A fixed tie rule assigns a point on a horizontal face to its upper slab, except the top. For this family, sorting the $m+1$ heights and binary searching gives $O(m)$ storage and $O(\log(m+1))$ queries, including the tie rule. This is a genuine restricted solution but elementary, not a claimed advance on arbitrary subdivisions.

The attempted general construction instead recursively bisects a bounding box by planes perpendicular to the $x$ axis, and stores in each leaf the cells that intersect it. For depth $h$, there are $2^h$ vertical leaf boxes. Every one of the $m$ slabs has an interior point in every leaf, so the lists contain exactly $m2^h$ incidences. If $h=\lceil\log_2m\rceil$, a query reaches a leaf in $O(\log m)$ steps but that leaf still contains all $m$ possible answers, and the lists use $\Theta(m^2)$ space. If lists are shared to reduce space, their logical candidate set still has size $m$; the navigation alone has not answered the query. This proves a precise failure of the inference that balanced geometric depth ensures balanced answer complexity.

To express the same issue in recurrence form, let $c(Q)$ be the number of original cells meeting a node box. A binary cut may have $c(Q_1)=c(Q_2)=c(Q)$, not $c(Q)/2$. Counting objects only at the root and tree depth therefore cannot justify linear storage. The slab family saturates this failure at every level of the displayed tree.

Choosing horizontal cuts repairs this family completely; hence the example does not defeat adaptive separators. What a successful adaptive proof must control is the total duplication over all cut cells as well as the number of query tests. Neither follows from balanced coordinates or a small tree depth.

Verification and adversarial audit

All cells are axis-aligned boxes, so the example satisfies the face-to-face input convention without hidden high-degree faces. Storage counts include every cell-to-leaf incidence. $m=1$ is constant size. Query points on slab boundaries were assigned explicitly. No universal separator lower bound is inferred.

Audit corrections.

A bad hierarchy was not promoted to a lower bound for arbitrary or adaptive data structures; full boundary-description size is counted.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The first gap is an adaptive construction with a proved linear duplication budget and logarithmic query depth for all polyhedral subdivisions. The favorable slab algorithm and the unfavorable perpendicular hierarchy do not settle existence of such a data structure in the requested model.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://topp.openproblem.net/p13 (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration and repository-format review; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved. This is a research attempt with an explicit failed route or restricted calculation, not a full solution, not a current-status certification, and not a claim that the elementary material is new. The catalogue's original source-status label is preserved independently of this attempt status.