ABSTRACT: Being motivated by the theory of flexible polyhedra we present an algorithm implemented in Mathematica that answers the question of whether a polyhedral surface in three-dimensional Euclidean space has self-intersections, and give an example of its application. The main feature of our algorithm is that its implementation uses only symbolic calculations, i.e., no floating point calculations are used. The point is that we consider the conclusions about the presence or absence of self-intersections of a polyhedral surface based on floating point calculations to be insufficiently rigorous for use in the theory of flexible polyhedra. The algorithm presented in this publication is the main tool for studying the presence or absence of self-intersections used in our original article. CITATION (original article): Alexandrov, V.A., Volokitin, E.P. An Embedded Flexible Polyhedron with Nonconstant Dihedral Angles. Sib Math J 65, 1259–1280 (2024). https://doi.org/10.1134/S003744662406003X

Introduction

In this publication, a compact polyhedral surface in Euclidean 3-space
3

with or without boundary, all of whose faces are triangles, and which a priori can have self-intersections of any type is called a polyhedron.​A polyhedron
P
is called flexible if its spatial shape can be changed continuously (i.e., without jumps) only by changing its dihedral angles, i.e., if
P
can be included in a continuous family of polyhedra
{
P
t
}
t∈[α,β)
such that
P=
P
α
and, for any
t∈(α,β)
,
P
α
and
P
t
are combinatorially equivalent, their corresponding faces are congruent, while
P
α
and
P
t
themselves are not congruent. We call such a family
{
P
t
}
t∈[α,β)
a flex of
P
, and we call
t
the parameter of the flex.​The first examples of flexible polyhedra without boundary in
3

were constructed by Raoul Bricard in 1897. All of them have self-intersections and are combinatorially equivalent to a regular octahedron (which is why they are called flexible octahedra). Moreover, in 1897 Bricard classified all flexible octahedra in
3

. Nowadays, flexible octahedra are commonly called Bricard octahedra. ​In 1977 Robert Connelly constructed a flexible polyhedron in
3

that is homeomorphic to a sphere and has no self-intersections. After that finding the theory of flexible polyhedra began to flourish. Through the efforts of many geometers it has been proven that flexible polyhedra have many remarkable properties. For example, for every orientable flexible polyhedron without boundary in
3

it was shown that its total mean curvature, oriented volume, and every Dehn invariant are preserved diring the flex.​At the same time, there are still many interesting open questions in the theory of flexible polyhedra. These include the following well-known problem originally posed by Idzhad Kh. Sabitov:PROBLEM 1: Is there a flexible polyhedron in
3

, without boundary and without self-intersections, for which all dihedral angles change during the flex?
In the original article, we explicitly construct a polyhedron
P
, which gives a positive solution of Problem 1. It has 26 vertices, 72 edges and 48 faces. We construct
P
in several steps starting from a flexible sphere-homeomorphic self-intersection-free polyhedron
S
with only 9 vertices, known as Steffen polyhedron (for the first time
S
was constructed by Klaus Steffen in 1978).
Our construction also involves a previously unknown modification
M
of Steffen polyhedron. So, we must be able to decide whether a given polyhedron has self-intersections. To simplify and unify reasoning in our original article, we describe an algorithm that makes it possible to solve the following problem for the above-mentioned polyhedra
S
,
M
and
P
(and, preferably, not only for them):
PROBLEM 2: Given a polyhedron
Q
in Euclidean 3-space, does it has self-intersections?
The problem of finding intersections and self-intersections of polyhedral surfaces arises in a variety of problems in mathematics and applied mathematics, computer graphics and video games. There are many variations of this problem and dozens of algorithms designed to solve them (see, the literature mentioned our original article). However, existing algorithms are not suitable for us for the following reasons:
◼
  • we want to solve Problem 2 without using floating point arithmetic, i.e., we allow ourselves to use only symbolic calculations (which we de facto execute in Mathematica);
    • ◼
  • we want the algorithm to be logically as transparent as possible, and therefore we do not analyze “exceptional cases”; instead, the algorithm must notify us of the occurrence of each such case (we mean that we are not interested in either complete automation of calculations or optimization of their complexity and speed).
    • Therefore, we are forced to develop our own algorithm, the description of which we proceed to.

    The Algorithm

    First of all, we use the following observation: A polyhedron
    Q
    in Euclidean 3-space has a point of self-intersection if and only if there are its face Δ (i.e., a triangle), its edge
    I
    (i.e., a straight line segment), and a point
    x∈Δ⋂I
    such that
    x
    is not a vertex of Δ and an end-point of
    I
    simultaneously. As a result, we reduce Problem 2 to the following
    PROBLEM 2*: Given a polyhedron
    Q
    in Euclidean 3-space, does there are its face Δ (i.e., a triangle), its edge
    I
    (i.e., a straight line segment), and a point
    x∈Δ⋂I
    such that
    x
    is not a vertex of Δ and, simultaneously, is not an end-point of
    I
    .
    The second observation we use requires the notion of the oriented volume of a tetrahedron. As is known, if
    x
    k
    =(
    x
    k,1
    ,
    x
    k,2
    ,
    x
    k,3
    )
    ,
    k=0,1,2,3
    , are position vectors of the vertices of a tetrahedron in
    3
    
    , then the oriented volume
    Vol(
    x
    0
    ,
    x
    1
    ,
    x
    2
    ,
    x
    3
    )
    of this tetrahedron can be calculated using one of the following formulas:
    Vol(
    x
    0
    ,
    x
    1
    ,
    x
    2
    ,
    x
    3
    )=
    1
    6
    1
    x
    0,1
    x
    0,2
    x
    0,3
    1
    x
    1,1
    x
    1,2
    x
    1,3
    1
    x
    2,1
    x
    2,2
    x
    2,3
    1
    x
    3,1
    x
    3,2
    x
    3,3
    =
    1
    6
    x
    1,1
    -
    x
    0,1
    x
    1,2
    -
    x
    0,2
    x
    1,3
    -
    x
    0,3
    x
    2,1
    -
    x
    0,1
    x
    2,2
    -
    x
    0,2
    x
    2,3
    -
    x
    0,3
    x
    3,1
    -
    x
    0,1
    x
    3,2
    -
    x
    0,2
    x
    3,3
    -
    x
    0,3
    Let a closed triangle
    Δ⊂
    3
    
    is given by the coordinates of its vertices
    y
    k
    =(
    y
    k,1
    ,
    y
    k,2
    ,
    y
    k,3
    )
    ,
    k=1,2,3
    and a closed straight line segment
    I⊂
    3
    
    is given by the coordinates of its
    z
    j
    =(
    z
    j,1
    ,
    z
    j,2
    ,
    z
    j,3
    )
    ,
    j=1,2
    .
    It is easy to understand that if both determinants
    6Vol(
    y
    1
    ,
    y
    2
    ,
    y
    3
    ,
    z
    1
    ),6Vol(
    y
    1
    ,
    y
    2
    ,
    y
    3
    ,
    z
    2
    )
    (
    1
    )
    are nonzero and have the same sign, then
    z
    1
    and
    z
    2
    lie strictly to one side of the plane containing Δ (see the left side of Fig. 1). Consequently, in this case
    I
    does not intersect the plane containing Δ, and hence
    I⋂Δ=ϕ
    .
    Figure 1. Various cases of mutual arrangement of a triangle Δ with vertices
    y
    1
    ,
    y
    2
    ,
    y
    3
    and a segment
    I
    with endpoints
    z
    1
    ,
    z
    2
    .
    If both determinants (1) are nonzero and have different signs, then
    z
    1
    and
    z
    2
    lie to opposite sides of the plane containing Δ (see the central and right parts of Fig. 1). In this case, to figure out whether
    I
    and Δ intersect, we need to calculate three more determinants:
    6Vol(
    z
    1
    ,
    z
    2
    ,
    y
    1
    ,
    y
    2
    ),6Vol(
    z
    1
    ,
    z
    2
    ,
    y
    2
    ,
    y
    3
    ),6Vol(
    z
    1
    ,
    z
    2
    ,
    y
    3
    ,
    y
    1
    )
    (
    2
    )
    If all determinants (2) are nonzero and have the same sign, then
    I⋂Δ≠ϕ
    . This situation is schematically shown in the central part of Fig. 1.
    If all three determinants in (2) are nonzero, but not all of them have the same sign, then
    I⋂Δ=ϕ
    .
    This situation is schematically shown in the right part of Fig. 1.
    There is also a possibility that at least one of the determinants in (1) and (2) is equal to zero. We call such a case “exceptional”. We expect that for the polyhedra
    M
    ,
    S
    and
    P
    , i.e., for the polyhedra of primary interest to us, there will be no “exceptional” cases at all or they will be very few so that we can study each of them individually.
    Therefore, in order to avoid complicating the algorithm, when encountering an “exceptional” case, our algorithm only states that the question of the existence of intersections of Δ and
    I
    requires additional study.
    For more details and proofs related to our algorithm, see Section 4 of the original article.

    Implementation of the algorithm in Wolfram

    We realize the algorithm described in Section 2 in Wolfram as the procedure selfintersectionQ, see Fig. 2.The procedure uses as arguments a list of edges s; a list of edges ss with the coordinates of the ends; a list of faces t; and a list of faces tt with the coordinates of the vertices of the polyhedron under consideration. These lists should be created before calling the procedure.The procedure returns a list whose elements are lists of the form
    {
    z
    i
    ,
    z
    j
    },{
    y
    k
    ,
    y
    l
    ,
    y
    m
    },Q
    or
    {
    z
    i
    ,
    z
    j
    },{
    y
    k
    ,
    y
    l
    ,
    y
    m
    },QQ
    .The element
    {
    z
    i
    ,
    z
    j
    },{
    y
    k
    ,
    y
    l
    ,
    y
    m
    },Q
    of the resulting list is equivalent to the message “The question whether the face with the vertices
    y
    k
    ,
    y
    l
    ,
    y
    m
    intersects the edge with the end-points
    z
    i
    ,
    z
    j
    requires additional study.”The element
    {
    z
    i
    ,
    z
    j
    },{
    y
    k
    ,
    y
    l
    ,
    y
    m
    },QQ
    of the resulting list is equivalent to the message “The face with the vertices
    y
    k
    ,
    y
    l
    ,
    y
    m
    and the edge with the end-points
    z
    i
    ,
    z
    j
    do intersect.”In particular, it follows from the above that if the list returned by the procedure selfintersectionQ turns out to be empty, then we can assert that the polyhedron under study has no self-intersections.
    In[]:=
    selfintersectionQ[s_,ss_,t_,tt_]:=Module[​​{message={},edge,face,l,det,det1,det2,det3,det4,det5,t1,t2,tt1,end},​​det[u1_List,u2_List,u3_List,w_List]:=​​Det[{{1,u1[[1]],u1[[2]],u1[[3]]},​​{1,u2[[1]],u2[[2]],u2[[3]]},​​{1,u3[[1]],u3[[2]],u3[[3]]},​​{1,w[[1]],w[[2]],w[[3]]}}];​​Do[​​edge=s[[i]];face=t[[j]];l=Intersection[edge,face];​​If[Length[l]===0,Continue,Goto[tt1]];​​edge=ss[[i]];​​face=tt[[j]];​​det1=det[face[[1]],face[[2]],face[[3]],edge[[1]]];​​det2=det[face[[1]],face[[2]],face[[3]],edge[[2]]];​​If[det1*det2===0,Continue,Goto[t1]];​​message=Append[message,{{i,j}," Q"}];​​Goto[end];​​Label[t1];​​If[det1*det2>0,Goto[end],Continue];​​det3=det[edge[[1]],edge[[2]],face[[1]],face[[2]]];​​det4=det[edge[[1]],edge[[2]],face[[2]],face[[3]]];​​det5=det[edge[[1]],edge[[2]],face[[3]],face[[1]]];​​If[det3*det4*det5===0,Continue,Goto[t2]];​​message=Append[message,{{i,j}," Q"}];​​Goto[end];​​Label[t2];​​If[Sign[det3]===Sign[det4]===Sign[det5],Continue,Goto[end]];​​message=Append[message,{{i,j}," QQ"}];​​Goto[end];​​Label[tt1];​​edge=ss[[i]];​​face=tt[[j]];​​If[Length[l]===1,Continue,Goto[end]];​​det1=det[face[[1]],face[[2]],face[[3]],edge[[1]]];​​det2=det[face[[1]],face[[2]],face[[3]],edge[[2]]];​​If[det1===0&&det2===0,Continue,Goto[end]];​​message=Append[message,{{i,j}," Q"}];​​Goto[end];​​Label[end],​​{i,1,Length[s]},{j,1,Length[t]}];​​Table[{s[[message[[k,1,1]]]],t[[message[[k,1,2]]]],​​message[[k,2]]},{k,1,Length[message]}]​​]
    Figure 2. Procedure selfintersectionQ.

    Application of the algorithm to Steffen polyhedron
    S

    In this Section we apply the procedure selfintersectionQ to Steffen polyhedron
    S
    . It is a well-known flexible polyhedron whose construction is described in many articles and books. The reader can find references to some of them in our original article. In this publication, we limit ourselves to the minimum information about
    S
    which is necessary for our purposes.
    Fig. 3 shows the development of Steffen polyhedron
    S
    . The reader can scan it and print it on thick paper at a larger scale. The development must be bent so that the internal dihedral angle of
    S
    is less than
    ∘
    180
    at the edges drawn by solid lines and is larger than
    ∘
    180
    at the edges drawn as dotted lines. The edges of the development with identical vertices need to be glued in pairs; more precisely, one must glue in pairs the edges connected to each other by circular arcs, two edges
    a
    3
    a
    9
    , and two edges
    a
    4
    a
    9
    . We believe that the model will help the reader understand what we are writing about.
    Let us introduce an orthogonal Cartesian coordinate system such that:
    {{{a2,a3},{a9,a7,a8},QQ},{{a7,a8},{a1,a2,a3},QQ}},
    The corresponding calculations and related comments are presented in the file steffen-1.nb attached.
    Finally, we mention that

    steffen-0.nb

    Square of the distance between points a, b
    We choose that of the two possible positions of the vertex a5 = (x, y, z) found above for which the y - coordinate is larger.
    We choose that of the two possible positions of the vertex a6 = (x, y, z) found above for which the y - coordinate is smaller.
    We choose that of the two possible positions of the vertex a7 = (x, y, z) found above for which the y - coordinate is larger.
    We choose that of the two possible positions of the vertex a8 = (x, y, z) found above for which the y - coordinate is smaller.
    Function vol[face_List] returns the oriented volume of the tetrahedron which has the origin as its apex and has the given triangle face as its base

    steffen-t.nb

    Square of the distance between points a, b
    We choose that of the two possible positions of the vertex a5 = (x, y, z) found above for which the y - coordinate is larger.
    We choose that of the two possible positions of the vertex a6 = (x, y, z) found above for which the y - coordinate is smaller .
    We choose that of the two possible positions of the vertex a7 = (x, y, z) found above for which the y - coordinate is larger.
    We choose that of the two possible positions of the vertex a8 = (x, y, z) found above for which the y - coordinate is smaller.

    CITE THIS NOTEBOOK

    Given a polyhedral surface, is it self-intersection-free?​
    by Victor Alexandrov & Evgenii Volokitin​
    Wolfram Community, STAFF PICKS, February 6, 2025
    ​https://community.wolfram.com/groups/-/m/t/3382354