pith. sign in

arxiv: 2607.01423 · v1 · pith:NVPKZIXCnew · submitted 2026-07-01 · 💻 cs.CG · cs.DM

On Reconstructing a Convex Polygon from Partial Information

Alexander Baumann , Therese Biedl , Mahmoud Elashmawi , Simon D. Fink , Maria Saumell , Andr\'e Schulz This is my paper

Pith reviewed 2026-07-03 00:52 UTC · model grok-4.3

classification 💻 cs.CG cs.DM
keywords convex polygon reconstructionpartial feature setsedge lengthspolygon anglescomputational geometrytesting algorithmshardness resultsopen problems
0
0 comments X

The pith

A systematic study determines for which one- or two-feature combinations a convex polygon can be reconstructed.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the task of building a convex polygon that matches one or two given ordered sets of its features, such as edge lengths or interior angles. It surveys previously known cases, supplies testing algorithms and hardness results for additional combinations, and flags many remaining cases as open. A sympathetic reader cares because the results clarify exactly which partial descriptions suffice to determine or construct such a polygon. The work assumes the supplied features are consistent with at least one convex polygon.

Core claim

The reconstruction problem asks to construct a (convex) polygon that has a specified set of features, such as an ordered set of edge-lengths or an ordered set of polygon-angles. In this paper, we do a systematic exploration of the reconstruction problem in all scenarios where one or two sets of features have been specified. Some of these scenarios were well-studied already, for some we develop testing-algorithms and/or hardness results, and many give rise to interesting open problems for future study.

What carries the argument

the reconstruction problem of building a convex polygon matching one or two ordered feature sets such as edge lengths or angles

Load-bearing premise

The supplied feature sets are ordered and come from some convex polygon.

What would settle it

A specific pair of feature types for which the paper supplies neither an algorithm nor a hardness proof nor labels the case open would show the exploration is incomplete.

Figures

Figures reproduced from arXiv: 2607.01423 by Alexander Baumann, Andr\'e Schulz, Mahmoud Elashmawi, Maria Saumell, Simon D. Fink, Therese Biedl.

Figure 1
Figure 1. Figure 1: Features of a star-shaped polygon (bold). [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A convex polygon that realizes given areas. [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Inductive construction of Theorem 2. Left: Base case. Middle/Right: Schematic inductive step [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Constructing a just-big-enough triangle at a local minimum among the edge distances. [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: More features of a star-shaped polygon. Corollary 10 The partial ray angle ρ − i and ρ + i lie in [0, 90◦ ) and respectively satisfy cos ρ − i ≥ hi/hi−1 and cos ρ + i ≥ hi/hi+1. Proof. This is implied by the two previous claims since cos is monotonically decreasing in the range [0, 90◦ ). □ C Missing Proofs of Section 3 C.1 Convex Realizations of Edge Distances In this section we prove the following result… view at source ↗
Figure 6
Figure 6. Figure 6: Moving the normal for one half-plane to make their intersection bounded. [PITH_FULL_IMAGE:figures/full_fig_p013_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: At an edge with locally minimal edge distance, the edge ray must hit the edge. [PITH_FULL_IMAGE:figures/full_fig_p013_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Constructing a rectangle for any four given edge distances. [PITH_FULL_IMAGE:figures/full_fig_p014_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: We can choose ε such that the sum of partial ray angles is exactly 360◦ . Place triangles T − 0 , T + 0 , T − 2 , . . . , T + k−2 so that they share the corner o, and such that T − 2j and T + 2j share the side of length h ′ 2j while T + 2j and T − 2j+2 share the side of length h ′ 2j+1 + ε. See also [PITH_FULL_IMAGE:figures/full_fig_p014_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Combining triangles to get a realization of the local minima. [PITH_FULL_IMAGE:figures/full_fig_p014_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Closeup: insert an edge for a local maximum. [PITH_FULL_IMAGE:figures/full_fig_p015_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Closeup: insert edges between a local minimum and a local maximum. [PITH_FULL_IMAGE:figures/full_fig_p015_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Configuration with flat angle θi(x). If i is odd, then from the propagation formula for ℓ = ±1 we have di+ℓ(x) = si+ℓx for some value si+ℓ that only depends on the input and can be computed in the WordRAM model. Hence, the flat angle happens if x 2 = 2(Ai−1+Ai)/si+1si−1, and to have a convex angle x 2 needs to be smaller than this. If i is even then similarly di+ℓ(x) = si+ℓ/x for ℓ ∈ {±1}, the flat angle … view at source ↗
Figure 14
Figure 14. Figure 14: Two choices for realizing corner distances and edge distances. [PITH_FULL_IMAGE:figures/full_fig_p018_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Construction of edge distances and corner distances for encoding the 2-partition instance [PITH_FULL_IMAGE:figures/full_fig_p019_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Two possibilities for the next corner, even if we know the previous one. [PITH_FULL_IMAGE:figures/full_fig_p019_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: NP-hardness construction. We show the flat cylinder; the standing cylinder is obtained by [PITH_FULL_IMAGE:figures/full_fig_p020_17.png] view at source ↗
read the original abstract

The reconstruction problem asks to construct a (convex) polygon that has a specified set of features, such as an ordered set of edge-lengths or an ordered set of polygon-angles. In this paper, we do a systematic exploration of the reconstruction problem in all scenarios where one or two sets of features have been specified. Some of these scenarios were well-studied already, for some we develop testing-algorithms and/or hardness results, and many give rise to interesting open problems for future study.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper claims to perform a systematic exploration of reconstructing convex polygons given one or two ordered feature sets (e.g., edge lengths, angles). It reviews previously studied scenarios, develops testing algorithms and/or hardness results for additional combinations, and identifies many open problems, with the input feature sets required to be consistent with some convex polygon.

Significance. If the algorithms and hardness results hold, the work organizes a broad family of reconstruction problems in computational geometry and supplies a useful map of solved cases versus open questions. The explicit consistency precondition avoids ill-posed instances and is a positive modeling choice.

minor comments (2)
  1. [Abstract] Abstract: the phrase 'testing-algorithms and/or hardness results' is vague; listing the specific feature-pair combinations that receive new results would help readers locate the contributions.
  2. The manuscript would benefit from a summary table that cross-references each feature combination with its status (known, new algorithm, hardness, open).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No circularity: enumeration of reconstruction variants with explicit assumptions

full rationale

The paper performs a systematic case-by-case exploration of convex polygon reconstruction from one or two ordered feature sets (e.g., edge lengths, angles). It states the consistency assumption explicitly as a precondition for the problem to be well-posed and develops testing algorithms or hardness results for various combinations, while noting open problems. No equations, fitted parameters, predictions, or self-citations form a load-bearing derivation chain that reduces to inputs by construction. The structure is enumerative and algorithmic rather than deductive, making the contribution self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no free parameters, axioms, or invented entities are described in the provided text.

pith-pipeline@v0.9.1-grok · 5618 in / 1036 out tokens · 24781 ms · 2026-07-03T00:52:12.698419+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 14 canonical work pages

  1. [1]

    Open problems from CCCG 2025

    Hugo Akitaya, Shahin Kamali, Seyed-Mohammad Seyed-Javadi, and Frederick Stock. Open problems from CCCG 2025. InProceedings of the 37th Annual Canadian Conference on Computational Geometry, CCCG 2025, August 13-15, 2025, York University, Toronto, Canada, 2025. URL: https://cccg.ca/proceedings/2025/CCCG2025-Proceedings.pdf

    2025

  2. [2]

    Polygon reconstruction from line cross- sections

    Gill Barequet, Craig Gotsman, and Avishay Sidlesky. Polygon reconstruction from line cross- sections. InProceedings of the 18th Annual Canadian Conference on Computational Geometry, CCCG 2006, August 14-16, 2006, Queen’s University, Ontario, Canada, 2006. URL: https://cccg. ca/proceedings/2006/cccg21.pdf

    2006

  3. [3]

    Reconstructing polygons from scanner data

    Therese Biedl, Stephane Durocher, and Jack Snoeyink. Reconstructing polygons from scanner data. Theoretical Computer Science, 412(32):4161–4172, July 2011.doi:10.1016/j.tcs.2010.10.026

    work page doi:10.1016/j.tcs.2010.10.026 2011

  4. [4]

    Chen and Haitao Wang

    Danny Z. Chen and Haitao Wang. An improved algorithm for reconstructing a simple polygon from its visibility angles.Computational Geometry, 45(5-6):254–257, 2012. doi:10.1016/j.comgeo.2012. 01.005

    work page doi:10.1016/j.comgeo.2012 2012

  5. [5]

    Rigidity of nonconvex polyhedra with respect to edge lengths and dihedral angles.Discrete & Computational Geometry, 74(2):302–336, 2025

    Yunhi Cho and Seonhwa Kim. Rigidity of nonconvex polyhedra with respect to edge lengths and dihedral angles.Discrete & Computational Geometry, 74(2):302–336, 2025. doi:10.1007/ S00454-024-00670-W

    2025

  6. [6]

    Coullard and Anna Lubiw

    Collette R. Coullard and Anna Lubiw. Distance visibility graphs.International Journal of Computa- tional Geometry & Applications, 2(4):349–362, 1992.doi:10.1142/S0218195992000202

    work page doi:10.1142/s0218195992000202 1992

  7. [7]

    A polygon is determined by its angles.Computa- tional Geometry, 44(8):418–426, October 2011.doi:10.1016/j.comgeo.2011.04.003

    Yann Disser, Mat´ uˇ s Mihal´ ak, and Peter Widmayer. A polygon is determined by its angles.Computa- tional Geometry, 44(8):418–426, October 2011.doi:10.1016/j.comgeo.2011.04.003

    work page doi:10.1016/j.comgeo.2011.04.003 2011

  8. [8]

    Polygons with Prescribed Angles in 2D and 3D.Journal of Graph Algorithms and Applications, 26(3):363–380, June 2022

    Alon Efrat, Radoslav Fulek, Stephen Kobourov, and Csaba T´ oth. Polygons with Prescribed Angles in 2D and 3D.Journal of Graph Algorithms and Applications, 26(3):363–380, June 2022. doi: 10.7155/jgaa.00599

    work page doi:10.7155/jgaa.00599 2022

  9. [9]

    Smoothing the gap between NP and ER

    Jeff Erickson, Ivor van der Hoog, and Tillmann Miltzow. Smoothing the gap between NP and ER. SIAM Journal on Computing, 53(6):FOCS20–102–FOCS20–138, 2024.doi:10.1137/20M1385287

    work page doi:10.1137/20m1385287 2024

  10. [10]

    How fast can we multiply large integers on an actual computer? InLATIN 2014: Theoretical Informatics, pages 660–670, Berlin, Heidelberg, 2014

    Martin F¨ urer. How fast can we multiply large integers on an actual computer? InLATIN 2014: Theoretical Informatics, pages 660–670, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg. doi:10.1007/978-3-642-54423-1_57

    work page doi:10.1007/978-3-642-54423-1_57 2014

  11. [11]

    M. R. Garey and D. S. Johnson.Computers and Intractability: A Guide to the Theory of NP- Completeness. Freeman, 1979

    1979

  12. [12]

    Goodman, Joseph O’Rourke, and Csaba D

    Jacob E. Goodman, Joseph O’Rourke, and Csaba D. T´ oth, editors.Handbook of discrete and computational geometry. CRC Press, Boca Raton London New York, third edition, 2018. 9

    2018

  13. [13]

    Ziegler.Convex polytopes

    Branko Gr¨ unbaum, Volker Kaibel, Victor Klee, and G¨ unter M. Ziegler.Convex polytopes. Springer, New York, 2003

    2003

  14. [14]

    Minkowski problems for geometric measures.Bulletin of the American Mathematical Society, 62(3):359–425, July 2025.doi:10.1090/bull/1858

    Yong Huang, Deane Yang, and Gaoyong Zhang. Minkowski problems for geometric measures.Bulletin of the American Mathematical Society, 62(3):359–425, July 2025.doi:10.1090/bull/1858

    work page doi:10.1090/bull/1858 2025

  15. [15]

    Dualising polyhedra, 2024

    Guy Inchbald. Dualising polyhedra, 2024. Web page last accessed April 2026. URL: https: //www.steelpillow.com/polyhedra/duality/duality.html

    2024

  16. [16]

    Lenhart and Sue Whitesides

    William J. Lenhart and Sue Whitesides. Reconfigurating closed polygonal chains in Euclidean d-space. Discrete & Computational Geometry, 13:123–140, 1995.doi:10.1007/BF02574031

    work page doi:10.1007/bf02574031 1995

  17. [17]

    Product Partition

    C. T. Ng, M. S. Barketau, T. C. E. Cheng, and Mikhail Y. Kovalyov. “Product Partition” and related problems of scheduling and systems reliability: Computational complexity and approximation. European Journal of Operational Research, 207(2):601–604, December 2010. doi:10.1016/j.ejor. 2010.05.034

    work page doi:10.1016/j.ejor 2010

  18. [18]

    Cyclic polygons with given edge lengths: Existence and uniqueness.Journal of Geometry, 82:156–171, 2005.doi:10.1007/s00022-005-1752-8

    Iosif Pinelis. Cyclic polygons with given edge lengths: Existence and uniqueness.Journal of Geometry, 82:156–171, 2005.doi:10.1007/s00022-005-1752-8

    work page doi:10.1007/s00022-005-1752-8 2005

  19. [19]

    PhD thesis, Yale University, 1978

    Michael Ian Shamos.Computational Geometry. PhD thesis, Yale University, 1978

    1978

  20. [20]

    Snoeyink

    J. Snoeyink. Cross-Ratios and Angles Determine a Polygon.Discrete & Computational Geometry, 22(4):619–631, December 1999.doi:10.1007/PL00009481

    work page doi:10.1007/pl00009481 1999

  21. [21]

    The discrete planar L0-Minkowski problem.Advances in Mathematics, 167(1):160–174, 2002.doi:10.1006/aima.2001.2040

    Alina Stancu. The discrete planar L0-Minkowski problem.Advances in Mathematics, 167(1):160–174, 2002.doi:10.1006/aima.2001.2040

    work page doi:10.1006/aima.2001.2040 2002

  22. [22]

    Geometry of planar graphs with angles

    Gopalakrishnan Vijayan. Geometry of planar graphs with angles. InProceedings of the Second Annual Symposium on Computational Geometry, SCG ’86, page 116–124, New York, NY, USA, 1986. Association for Computing Machinery.doi:10.1145/10515.10528. 10 A Further Related Results The literature on reconstruction problems in the plane is quite rich, and there are ...

    work page doi:10.1145/10515.10528 1986

  23. [23]

    3.I ′ = (h′ 0,

    The reduced instanceI ′ has a convex realization. 3.I ′ = (h′ 0, . . . , h′ k−1)either has size 3, or satisfies Pk/2−1 j=0 (ψ+1 2j + ψ−1 2j ) < 360◦ where ψℓ 2j (for ℓ = ±1) is the solution toarccos(h ′ 2j/h′ 2j+ℓ)in(0,90 ◦). 4.I ′ has a convex realization where edge rays hit the interior of their edges. The rest of this subsection is devoted to the (leng...

  24. [24]

    Definen new 1 := − 1 2(n′ 0 +n ′

  25. [25]

    and note that this lies betweenn ′ 0 andn ′ 2 in ccw order and forms angles less than 180 ◦ with both. If we hence remove from P ′ the half-plane defined byn ′ 1 and add to it the half-plane defined byn new 1 and the corresponding edge distance, then the intersection of these half-spaces is a realization ofI ′. For the next implication we need an insight ...

  26. [26]

    , ℓ) between the two edges e′ 0 and e′ 1 that realized edge distance h′ 0 and h′

    (Recall that all distances are distinct, which is crucial in this construction.) So we must add a new edge ei (for i = 1, . . . , ℓ) between the two edges e′ 0 and e′ 1 that realized edge distance h′ 0 and h′

  27. [27]

    Let c′ 1 be the corner between e′ 0 and e′ 1, and x0 and x1 be the tangent points of these edges

    Consider Figure 12. Let c′ 1 be the corner between e′ 0 and e′ 1, and x0 and x1 be the tangent points of these edges. Imagine sliding a segment e = ab where initially a=x 0 andb=c ′ 1, at the enda=c ′ 1 andb=x 1, and the points move at uniform speed. h′ 0 o h′ 1 x0 x1 c′ 1 h1 hℓ Figure 12: Closeup: insert edges between a local minimum and a local maximum....

  28. [28]

    So in particular both x0 and x1 remain as points on e′ 0 and e′

  29. [29]

    corner vectors and areas

    Therefore, the edges that we added here do not interfere with any edges that we might add for some other minimum-maximum pair elsewhere. Hence, repeating this approach at all other such pairs gives (1). We note that this construction crucially needs distinct edge distances; it is not clear how one could insert two equidistant edges if flat angles are not ...

  30. [30]

    corner vectors and edge distance

    Once we know ci, edge ei can have either increasing or decreasing slope; either way it forms a right triangle with the horizontal through ci and the (vertical) corner ray for ci+1. The distance between the corner rays is 4 ai, and the vertical distance between ci and ci+1 hence p ℓ2 i −(4a i)2 = 3ai. Thus, ei either adds or subtracts 3 ai to the y-coordin...