pith. machine review for the scientific record. sign in

arxiv: 2604.05786 · v1 · submitted 2026-04-07 · 💻 cs.CG

Recognition: no theorem link

Realizing Planar Linkages in Polygonal Domains

Thomas Depian , Carolina Haase , Martin N\"ollenburg , Andr\'e Schulz
Authors on Pith no claims yet

Pith reviewed 2026-05-10 18:31 UTC · model grok-4.3

classification 💻 cs.CG
keywords linkage realizationpolygonal domainplanar straight-line embeddingparameterized complexityNP-hardnessW[1]-hardnessXPunit lengths
0
0 comments X

The pith

Realizing a linkage inside a polygonal domain is W[1]-hard in the number of vertices even for unit lengths and no prescribed positions.

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

The paper studies the computational complexity of deciding whether a graph with given edge lengths can be drawn as a straight-line planar embedding strictly inside a given open polygonal region, possibly with some vertex positions fixed in advance. It establishes that the general problem lies in XP and is W[1]-hard when parameterized by the number of vertices, even when every edge has length exactly one and no positions are prescribed. For linkages that form a single path with fixed start and end points and unit lengths, the problem is NP-hard in arbitrary polygonal domains, yet becomes solvable in linear time when the path has only three edges and the domain is convex. These results map out the transition from intractable to tractable instances of linkage realization under geometric confinement.

Core claim

We show XP-membership and W[1]-hardness with respect to the size of G, even if ℓ ≡ 1 and no vertex positions are prescribed. Furthermore, we consider the case where G is a path with prescribed start and end position and ℓ ≡ 1. Despite the absence of any rigid components, we obtain NP-hardness in general, and provide a linear-time algorithm for arbitrary ℓ if G has only three edges and P is convex.

What carries the argument

The linkage realization problem inside an open polygonal domain P, which uses the interior geometry of P to enforce global planarity and length constraints while allowing reductions that encode combinatorial hardness.

If this is right

  • The hardness persists for completely flexible linkages that contain no rigid subgraphs.
  • Prescribing only the two endpoints of a path is already enough to make the realization question NP-hard inside general polygons.
  • Convexity of the domain together with a constant number of edges restores linear-time solvability even for arbitrary edge lengths.
  • The results separate the source of hardness from rigidity: the interaction between the linkage and the domain boundary suffices.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar parameterized hardness may hold when the domain is required to be simply connected or when a small number of interior obstacles are added.
  • It would be natural to ask whether the three-edge linear-time result extends to a constant number of edges inside polygons of bounded complexity.
  • The same geometric encoding technique might yield hardness for approximate realization or for maximizing the number of vertices that fit inside a fixed domain.

Load-bearing premise

The domain P must be open and every valid realization must lie strictly inside P without touching the boundary, so that reductions can place vertices and edges to simulate choices without violating planarity or escaping the region.

What would settle it

An algorithm that, for any fixed number of vertices, decides in polynomial time whether a unit-length linkage realizes inside a given polygonal domain, or an explicit small instance with five vertices where no such realization exists despite satisfying all local length and non-crossing conditions.

Figures

Figures reproduced from arXiv: 2604.05786 by Andr\'e Schulz, Carolina Haase, Martin N\"ollenburg, Thomas Depian.

Figure 1
Figure 1. Figure 1: Thus, we can move g by at most 2ε in any direction. To prevent g from using points (a ′ , b′ ) ∈/ Si,j we need to choose ε small enough, such that the distance between points (a, b) ∈ Ri,j is smaller than 4ε. We set the distance between the points to w m , where w is the width of the edges in P ′ . Thus, we need 4ε < w m [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 1
Figure 1. Figure 1: (a) The movement of g is restricted by the movement of t1, t2; (b) the longest distance in the areas T1 and, T2 is 2ε. Note also that no two grid vertices can be in the same grid square, as their triangles would cross. Lastly, for our construction to work as intended, we have to choose the width w of the edges of P ′ such that if a point (a, b) is used by a grid vertex gi,j in Ri,j then a grid vertex gi,j+… view at source ↗
Figure 2
Figure 2. Figure 2: We can calculate b and c using the following equations: c = p 4(1 − w2) and b = √ 4 − w2. The longest vertical distance that gi+1,j can be away from a point (a ′ , b) in Ri+1,j is b−c. Hence, we need b−c = √ 4 − w2− p 4(1 − w2) < w m , which we can solve for w [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 2
Figure 2. Figure 2: Calculate width of edges of P ′ The theorem follows from Lemmas 1 and 2. Theorem 2. Planar Linkage Realizability is W[1]-hard with respect to the number nG of vertices of G. 5 Realizing Linear Unit-Length Linkages is NP-hard Theorem 2 rules out fixed parameter tractable algorithms for all common graph parameters. However, similar to previous reductions [2, 10], the constructed graph G still contains rigid … view at source ↗
Figure 3
Figure 3. Figure 3: (a) Construction for k = 3 and m = 2, P ′ highlighted in orange, grid squares marked in light blue. (b) If the blue point with tuple (2, 2) is chosen, then to the right only points in the red area with tuples (x, 2), 1 ≤ x ≤ m can be used. (c) Grid Tiling instance of the construction in (a). (a) (b) x1 x2 x3 x4 x1 ∨ x2 ∨ x4 ¬x1 ∨ ¬x2 ∨ ¬x3 x2 ∨ x3 ∨ x4 v1 vn [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A (a) formula φ and the (b) schematization of the constructed instance [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A (a) tunnel, (b) bend, (c) and the main part of a shifter with configurations through them. We hatch in this and the following figures the outside of the polygonal domain if there is risk of confusion. (or down) by 0.2. The shifter consists of the main part from Figure 5c on whose two sides we attach a tunnel that help us establish correctness. Clause Gadget. The main part of the clause gadget for the cla… view at source ↗
Figure 6
Figure 6. Figure 6: (a)–(d) Different configurations Γ through the main part of the clause gadget. Dashed lines indicate different possibilities for the configuration to pass through the corridors. the other hand, if Γ enters the main part via → i,1 or → k,1 , it uses a corridor that does not intersect with the one(s) for → j,0 , allowing a planar configuration even if Γ enters the main part via → j,0 . The corridor connectin… view at source ↗
Figure 7
Figure 7. Figure 7: A segment of length one can only have endpoints in two corridors if γ ≤ 2 arcsin 2αε. some v ′ ∈ V (G) with Γ(v ′ ) ∈ → i,t(C ′ ). Furthermore, there is some v ′′ ∈ V (G) such that Γ(v ′′) ∈ → z,1 (C ′ ) for some z ∈ {i, j, k}. We attach on the left and right side of the main part two shifters, and at the bottom side two tunnels each to obtain the clause gadget and unify the entrance and exit areas. Variab… view at source ↗
Figure 8
Figure 8. Figure 8: The (a) first and (b) third component of the variable gadget for x1 and xi, respectively We now combine the above-introduced gadgets by taking a suitable scaled planar rectilinear drawing E of the incidence graph of φ, replacing all components with the respective gadgets, and unifying all vertices in different gadgets that lie on the same point. To finish the construction of (L, P, V ′ , δ), we close the f… view at source ↗
Figure 9
Figure 9. Figure 9: Realizing a three-edge linkage. It suffices to check these types of configurations; see Theorem 4. The polygonal domain is hinted by the gray areas. (i) v2 or v3 hit the boundary of P, (ii) two incident edges become co-linear, or (iii) v1 lies on Γ(v3v4) or v4 lies on Γ(v1v2); see [PITH_FULL_IMAGE:figures/full_fig_p017_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: A visualization of (x, y)ε. Crosses indicate the four points (x, y) T ε , (x, y) R ε , (x, y) B ε , and (x, y) L ε and colors the quadrants of (x, y)ε. To facilitate the following detailed description of the gadget, we assume that the lower-left corner of each gadget is placed at the origin (0, 0). However, this is without loss of generality, as our constructions are agnostic to translations and rotations… view at source ↗
Figure 11
Figure 11. Figure 11: A (a) tunnel, (b) bend, (c) and shifter with possible configurations through them. We hatch in this and the following figures the outside of the polygonal domain if there is risk of confusion. Tunnels. We discuss tunnels that run horizontally from left to right; other axis-aligned tunnels can be constructed by rotating or inverting the following construction. A tunnel T is a sawtooth-like shaped part of t… view at source ↗
Figure 12
Figure 12. Figure 12: A visualization of the procedure to find the configuration Γ ′ with Γ ′ (v) = (x, y) ∈ → ¬x(T). (a) For a point (x, 0), we can shift the “standard” configuration for (0, 0) horizontally by x, indicated in orange. (b) For the general point (x, y), we use the approach in (a) to find an initial configuration that still has to be shifted upwards (see the dashed configuration) and rotated accordingly. We obser… view at source ↗
Figure 13
Figure 13. Figure 13: We place the corridors in a way such that every start and end area [PITH_FULL_IMAGE:figures/full_fig_p028_13.png] view at source ↗
Figure 13
Figure 13. Figure 13: Conversely, i.e., if Γ enters via → xj ,1 , there is again only one corridor, namely (CC7), giving the configuration little freedom in placing the remaining vertices. This, of course, relies on the assumption that the configuration cannot leave or even change its intended corridor. To this end, we now argue that for a suitable small constant ε it is not possible to enter the clause gadget at some entrance… view at source ↗
Figure 14
Figure 14. Figure 14: The (a) first and (b) third component of the variable gadget for x1 and xi, respectively, together with parts of the unit cycles used in the placement of the vertices of P and the arguments in Lemma 7. In (a) we color the different regions → x1 is composed of in different shades of purple. In (b), we mark in blue the intersections of the unit circles mentioned in the proof of Lemma 7. The entrance area of… view at source ↗
read the original abstract

A linkage $\mathcal{L}$ consists of a graph $G=(V,E)$ and an edge-length function $\ell$. Deciding whether $\mathcal{L}$ can be realized as a planar straight-line embedding in $\mathbb{R}^2$ with edge length $\ell(e)$ for all $e \in E$ is $\exists\mathbb{R}$-complete [Abel et al., JoCG'25], even if $\ell \equiv 1$, but a considerable part of $\mathcal{L}$ is rigid. In this paper, we study the computational complexity of the realization question for structurally simpler, less rigid linkages inside an open polygonal domain $P$, where the placement of some vertices may be specified in the input. We show XP-membership and W[1]-hardness with respect to the size of $G$, even if $\ell \equiv 1$ and no vertex positions are prescribed. Furthermore, we consider the case where $G$ is a path with prescribed start and end position and $\ell \equiv 1$. Despite the absence of any rigid components, we obtain NP-hardness in general, and provide a linear-time algorithm for arbitrary $\ell$ if $G$ has only three edges and $P$ is convex.

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 manuscript studies the computational complexity of realizing a linkage (a graph G with edge lengths ℓ) as a planar straight-line embedding strictly inside an open polygonal domain P, where some vertices may have prescribed positions. It establishes XP-membership and W[1]-hardness parameterized by |V(G)|, even when ℓ ≡ 1 and no positions are fixed. For the special case of path linkages with fixed endpoints and unit lengths, it proves NP-hardness in general via a 3-SAT reduction, while providing a linear-time algorithm when |E| = 3 and P is convex.

Significance. If the results hold, this work meaningfully refines the complexity map for linkage realization by isolating the effects of domain constraints and reduced rigidity. The explicit XP algorithm via bounded enumeration of vertex-order types inside P, the W[1]-hardness reduction using unit-length gadgets along the boundary, and the linear-time sweep for the three-edge convex case are concrete strengths that provide both negative and positive results without relying on rigid substructures.

minor comments (2)
  1. [§3] §3 (XP membership): the enumeration of order types is described at a high level; adding a brief pseudocode sketch or a small worked example would improve readability without altering the argument.
  2. [§5] The statement of the linear-time algorithm for |E|=3 (convex P) would benefit from an explicit statement of the running-time constant or the sweep primitives used, to make the O(n) claim fully transparent.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript and for recommending minor revision. The summary accurately captures the main contributions: the XP-membership and W[1]-hardness results for general linkages (even with unit lengths and no fixed positions), the NP-hardness for unit-length paths with fixed endpoints, and the linear-time algorithm for three-edge paths in convex polygons. We appreciate the recognition that these results help refine the complexity map without relying on rigid substructures.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's core results—XP-membership via bounded combinatorial enumeration of vertex-order types inside P, W[1]-hardness via a gadget reduction along the boundary, NP-hardness for paths via 3-SAT reduction staying strictly inside the open domain, and the linear-time algorithm for |E|=3 in convex P—are established through independent geometric reductions and direct algorithmic constructions. No step reduces by definition to its inputs, renames a known result, or relies on a load-bearing self-citation chain; the cited ∃R-completeness result is external and not used to derive the new claims.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard complexity-theoretic assumptions and geometric embedding definitions; no free parameters or invented entities are introduced.

axioms (2)
  • domain assumption Standard assumptions of parameterized complexity theory (FPT vs W[1]-hardness, XP membership)
    Invoked to classify the parameterized complexity of the realization problem.
  • standard math NP-hardness reductions are valid when the target problem is in NP
    Used for the path-with-fixed-endpoints hardness result.

pith-pipeline@v0.9.0 · 5525 in / 1370 out tokens · 56876 ms · 2026-05-10T18:31:38.848289+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

31 extracted references · 20 canonical work pages

  1. [1]

    and Demaine, Martin L

    Abel, Z., Demaine, E.D., Demaine, M.L., Eisenstat, S., Lynch, J., Schardl, T.B.: Who Needs Crossings? Hardness of Plane Graph Rigidity. In: Fekete, S.P., Lu- biw, A. (eds.) Proc. 32nd International Symposium on Computational Geometry (SoCG’16). LIPIcs, vol. 51, pp. 3:1–3:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016). https://doi.org/10.4230...

    work page doi:10.4230/lipics.socg.2016.3 2016

  2. [2]

    Journal of Computational Geometry16(2025)

    Abel, Z., Demaine, E.D., Demaine, M.L., Eisenstat, S., Lynch, J., Schardl, T.B.: Who needs crossings?: Noncrossing linkages are universal, and deciding (global) rigidity is hard. Journal of Computational Geometry16(2025). https://doi.org/ 10.20382/JOCG.V16I1A12

    work page doi:10.20382/jocg.v16i1a12 2025

  3. [3]

    TheoretiCS3(2024)

    Abrahamsen, M., Miltzow, T., Seiferth, N.: Framework for∃∖-completeness of two-dimensional packing problems. TheoretiCS3(2024). https://doi.org/10. 46298/THEORETICS.24.11

    2024

  4. [4]

    In: Fortune, S

    Alt, H., Knauer, C., Rote, G., Whitesides, S.: The complexity of (un)folding. In: Fortune, S. (ed.) Proc. 19th International Symposium on Computational Geometry (SoCG’03). pp. 164–170. ACM (2003). https://doi.org/10.1145/777792.777818 Realizing Planar Linkages in Polygonal Domains 19

    work page doi:10.1145/777792.777818 2003

  5. [5]

    In: Aichholzer, O., Wang, H

    Angelini, P., Cornelsen, S., Haase, C., Hoffmann, M., Katsanou, E., Montecchi- ani, F., Steiner, R., Symvonis, A.: Geometric realizations of dichotomous ordi- nal graphs. In: Aichholzer, O., Wang, H. (eds.) Proc. 41st International Sym- posium on Computational Geometry (SoCG’25). LIPIcs, vol. 332, pp. 9:1–9:16. Schloss Dagstuhl – Leibniz-Zentrum für Infor...

    2025

  6. [6]

    van Kreveld, and Mark H

    de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geome- try: Algorithms and Applications (3rd Edition). Springer (2008). https://doi.org/ 10.1007/978-3-540-77974-2

    work page doi:10.1007/978-3-540-77974-2 2008

  7. [7]

    International Journal of Computational Geometry and Application22(03), 187–205 (2012)

    de Berg, M., Khosravi, A.: Optimal Binary Space Partitions for Segments in the Plane. International Journal of Computational Geometry and Application22(03), 187–205 (2012). https://doi.org/10.1142/s0218195912500045

    work page doi:10.1142/s0218195912500045 2012

  8. [8]

    Discrete Applied Mathematics117(1–3), 293–297 (2002)

    Biedl, T., Demaine, E., Demaine, M., Lazard, S., Lubiw, A., O’Rourke, J., Robbins, S., Streinu, I., Toussaint, G., Whitesides, S.: A note on reconfiguring tree linkages: trees can lock. Discrete Applied Mathematics117(1–3), 293–297 (2002). https: //doi.org/10.1016/s0166-218x(01)00229-3

    work page doi:10.1016/s0166-218x(01)00229-3 2002

  9. [9]

    In: Liotta, G

    Cabello, S., Demaine, E.D., Rote, G.: Planar Embeddings of Graphs with Spec- ified Edge Lengths. In: Liotta, G. (ed.) Proc. 11th International Symposium on Graph Drawing and Network Visualization (GD’03). LNCS, vol. 2912, pp. 283–

  10. [10]

    https://doi.org/10.1007/978-3-540-24595-7_26

    Springer (2004). https://doi.org/10.1007/978-3-540-24595-7_26

    work page doi:10.1007/978-3-540-24595-7_26 2004

  11. [11]

    Journal of Graph Algorithms and Applications11(1), 259–276 (2007)

    Cabello, S., Demaine, E.D., Rote, G.: Planar Embeddings of Graphs with Speci- fied Edge Lengths. Journal of Graph Algorithms and Applications11(1), 259–276 (2007). https://doi.org/10.7155/jgaa.00145

    work page doi:10.7155/jgaa.00145 2007

  12. [12]

    Discrete & Computational Geometry30(2), 205–239 (2003)

    Connelly, R., Demaine, E.D., Rote, G.: Straightening Polygonal Arcs and Con- vexifying Polygonal Cycles. Discrete & Computational Geometry30(2), 205–239 (2003). https://doi.org/10.1007/S00454-003-0006-7

    work page doi:10.1007/s00454-003-0006-7 2003

  13. [13]

    Fomin and Lukasz Kowalik and Daniel Lokshtanov and D

    Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015). https:// doi.org/10.1007/978-3-319-21275-3

    work page doi:10.1007/978-3-319-21275-3 2015

  14. [14]

    Cambridge University Press (2007)

    Demaine, E.D., O’Rourke, J.: Geometric Folding Algorithms: Linkages, Origami, Polyhedra. Cambridge University Press (2007). https://doi.org/10.1017/ cbo9780511735172

    2007

  15. [15]

    Dis- crete Applied Mathematics28(2), 111–134 (1990)

    Eades, P., Wormald, N.C.: Fixed edge-length graph drawing is NP-hard. Dis- crete Applied Mathematics28(2), 111–134 (1990). https://doi.org/10.1016/ 0166-218x(90)90110-x

    1990

  16. [16]

    SIAM Journal on Computing53(6), S20–102 (2024)

    Erickson, J., van der Hoog, I., Miltzow, T.: Smoothing the gap between NP and ER. SIAM Journal on Computing53(6), S20–102 (2024). https://doi.org/10.1137/ 20M1385287

    2024

  17. [17]

    Journal of Symbolic Computation5(1–2), 37–64 (1988)

    Grigoriev, D., Jr., N.N.V.: Solving systems of polynomial inequalities in subex- ponential time. Journal of Symbolic Computation5(1–2), 37–64 (1988). https: //doi.org/10.1016/s0747-7171(88)80005-1

    work page doi:10.1016/s0747-7171(88)80005-1 1988

  18. [18]

    SIAM Journal on Computing13(3), 610–629 (1984)

    Hopcroft, J., Joseph, D., Whitesides, S.: Movement Problems for 2-Dimensional Linkages. SIAM Journal on Computing13(3), 610–629 (1984). https://doi.org/10. 1137/0213038

    1984

  19. [19]

    SIAM Journal on Computing14(2), 315–333 (1985)

    Hopcroft, J., Joseph, D., Whitesides, S.: On the Movement of Robot Arms in 2-Dimensional Bounded Regions. SIAM Journal on Computing14(2), 315–333 (1985). https://doi.org/10.1137/0214025

    work page doi:10.1137/0214025 1985

  20. [20]

    In: Proc

    Joseph, D.A., Plantings, W.H.: On the Complexity of Reachability and Motion Planning Questions (Extended Abstract). In: Proc. 1st International Symposium on Computational Geometry (SoCG). pp. 62–66. ACM (1985). https://doi.org/10. 1145/323233.323242 20 T. Depian, C. Haase, M. Nöllenburg, A. Schulz

    work page arXiv 1985

  21. [21]

    Discrete & Com- putational Geometry7(1), 69–76 (1992)

    Kantabutra, V.: Motions of a short-linked robot arm in a square. Discrete & Com- putational Geometry7(1), 69–76 (1992). https://doi.org/10.1007/bf02187825

    work page doi:10.1007/bf02187825 1992

  22. [22]

    Topology41(6), 1051–1107 (2002)

    Kapovich, M., Millson, J.J.: Universality theorems for configuration spaces of planar linkages. Topology41(6), 1051–1107 (2002). https://doi.org/10.1016/ s0040-9383(01)00034-9

    2002

  23. [23]

    Proceedings of the London Mathematical Society1(1), 213–216 (1875)

    Kempe,A.B.:OnaGeneralMethodofdescribingPlaneCurvesofthenthdegreeby Linkwork. Proceedings of the London Mathematical Society1(1), 213–216 (1875). https://doi.org/10.1112/plms/s1-7.1.213

    work page doi:10.1112/plms/s1-7.1.213

  24. [24]

    In: Biedl, T., Kerren, A

    Lubiw, A., Miltzow, T., Mondal, D.: The complexity of drawing a graph in a polyg- onal region. In: Biedl, T., Kerren, A. (eds.) Proc. 26th International Symposium on Graph Drawing and Network Visualization (GD’18). pp. 387–401. Lecture Notes in Computer Science, Springer (2018). https://doi.org/10.1007/978-3-030-04414-5_ 28

    work page doi:10.1007/978-3-030-04414-5_ 2018

  25. [25]

    Journal of Graph Algorithms and Applications26(4), 421–446 (2022)

    Lubiw, A., Miltzow, T., Mondal, D.: The complexity of drawing a graph in a polygonal region. Journal of Graph Algorithms and Applications26(4), 421–446 (2022). https://doi.org/10.7155/jgaa.00602

    work page doi:10.7155/jgaa.00602 2022

  26. [26]

    In: Sack, J., Urrutia, J

    Mitchell, J.S.B.: Geometric Shortest Paths and Network Optimization. In: Sack, J., Urrutia, J. (eds.) Handbook of Computational Geometry, chap. 15, pp. 633–701. Elsevier (2000). https://doi.org/10.1016/b978-044482537-7/50016-4

    work page doi:10.1016/b978-044482537-7/50016-4 2000

  27. [27]

    Springer (1985)

    Preparata, F.P., Shamos, M.I.: Computational Geometry - An Introduction. Springer (1985). https://doi.org/10.1007/978-1-4612-1098-6

    work page doi:10.1007/978-1-4612-1098-6 1985

  28. [28]

    standard

    Whitesides, S., Pei, N.: On the Reconfiguration of Chains (Extended Abstract). In: Cai, J., Wong, C.K. (eds.) Proc. 2nd International Computing and Combinatorics Conference (COCOON’96). Lecture Notes in Computer Science, vol. 1090, pp. 381–390. Springer (1996). https://doi.org/10.1007/3-540-61332-3_172 Realizing Planar Linkages in Polygonal Domains 21 A D...

    work page doi:10.1007/3-540-61332-3_172 1996

  29. [29]

    Towardsconstructingthesecondcorridor,(CC2),letc 1 bethe(unique)cross- ing of the two unit-disks positioned at(0,0.6)and(0,1)that lies insideB

    We perform symmetrically forR2 1 and take the union ofR1 1 andR 2 1 without the “cut-off” from the triangles as (CC1). Towardsconstructingthesecondcorridor,(CC2),letc 1 bethe(unique)cross- ing of the two unit-disks positioned at(0,0.6)and(0,1)that lies insideB. Sim- ilarly, letc 2 be the (unique) crossing of the two unit-disks positioned at(0,1)R ε and(0,...

  30. [30]

    cut-away

    To complete the construction of (CC5), we enlarge all rectangles such that they full-intersect at their ends Observe that (CC5) leans to the left and does not intersect (CC1). Corridor (CC6) is a symmetric (and mirrored) copy of (CC5) and it remains to construct (CC7). For the corridor (CC7), we takeR1 7, place its lower-left corner at(0.2,0)R ε and rotat...

  31. [31]

    From this on, Lemma 3 allows us to once more finalize the construction ofΓ ′ and we get Γ ′(vi+7)∈ → ¬xj (C)

    To finalize the construction ofΓ ′, we observe thatΓ(v i+5) = (5,0)∈ → ¬xj (T2), for the second tunnelT 2 attached toC ′. From this on, Lemma 3 allows us to once more finalize the construction ofΓ ′ and we get Γ ′(vi+7)∈ → ¬xj (C). If the configuration should lean to the right, as in Figure 6b, we perform symmetrically. The last case withp∈ → y(C)can be h...