Embeddings

Naively, a polytope is a collection of regions. This concept of polytope as a collection of non-overlapping convex regions has the advantage of specifying the surface. However, I would prefer to define a polytope as a collection of qualities, such as facet relations, convexity, and colinearity. Rather than list and define every quality of polytopes, it is easier to define transformations of region sets, and define an invariant for those transformations. Given a set of regions, I can add a boundary and the shape of the result is unchanged. Similarly, I can move a boundary, and even cause a migration of the underlying space without changing the shape of the polytope embedded in the space. Start with a partition of the regions in the polytope that excludes unnecessary boundaries, and specifies which portions of the boundaries are relevant. This sort of partition is explained in the prior post, "Polytopes, Convexity, Colinearity". Consider the power set of the partition. Choose those elements of the power set that form (convex) super-regions. Each of these elements has well defined sidedness wrt a subset of boundaries in the original space. Define a tristate space as a sidedness space where some sidednesses are left undefined. Map the chosen power set elements to regions in a tristate space. I claim this tristate space is invariant as required. It remains to pick a few polytope qualities and prove that region sets different in those qualities have different tristate spaces. Deferring that task, I'd prefer to identify conditions upon tristate spaces sufficient to embed them into linear spaces. Then I could count all possible polytopes of a given dimension and complexity. Define a tristate subspace as a tristate space with a set of boundaries removed, and identical regions combined. Define a linear subspace as a tristate subspace without undefined sidedness. Define a trispace subregion as one with a superset of defined sidedness. Read top-level region as one without subregions. I claim a tristate space is embeddable iff the sum of f(g(r),n) over all top-level regions r in any tristate subspace is equal to f(m,n), where m is the number of boundaries in the tristate subspace, f is the number of regions in a linear space, and g(r) is the number of boundaries in the tristate subspace r is undefined wrt. To prove this, construct the embedding by combining all linear subspaces of the tristate space. Because simplex spaces are unique up to automorphism, each boundary of the tristate space is included in a linear subspace. The resulting recombined space is linear because its subspaces are linear, and it is an embedding because its boundaries have the same sidedness.

Perspective

A complement of a region is the region separated by all boundaries. A subsection is a section or a section of a subsection. An n-section is an n-dimensional subsection. A shell of a region is all regions attached to the region.

Complement Region Theorem

The complement of each outside region is outside, and the complement of each inside region is empty.

Consider a 1-dimensional subsection L with outside region isomorphic to an outside region R. The hops of L are ordered. The first hop of L is a hop across a boundary of the shell of R. Each hop reverses the sidedness of another boundary, and L hops across each boundary once and only once. The last hop of L reverses the last boundary, bringing us to the complement of R. Thus the other outside region of L is isomorphic to the complement of R. By the Complement Region Lemma (unproven), the complement of R is outside.
Suppose regions R₀ and R₁ are complementary, and R₀ is inside. By the Subsection Theorem (unproven), there is a 1-dimensional subsection L with regions isomorphic to R₀ and R₁. Since R₀ is inside, the number of boundary reversals between R₀ and R₁ is not all, so they are not complementary.


Consider a set of regions as a polytope. In the section by a boundary, of the space with the boundary removed, facet regions are those isomorphic to regions with both polytope and non-polytope subregions.

A perspective is determined by a choice of outside region, the region containing the focal point. Assume the regions in a polytope have "nearness" of "true". For each region R₀ in the polytope with neighbor R₁ not in the polytope separated by boundary B, find whether the perspective region is on the same side of B as R₁, and xor that with nearness of R₀. Then take the section by B of the space with B removed, and use the xor result as nearness for the facet region isomorphic to R₀ and R₁. Choose any outside region for perspective in the section. Nearness of the only region in a 0-section determines whether it is an entry or exit. Thus, 1-sections get direction, 2-sections get clockwisedness. A necessary condition for visibility of a facet is that the facet is nearer than its polytope region. By the Perspective Theorem below, facets may be ordered by a topological sort of 1-sections from the perspective region to its complement. This is useful in computer graphics.

Perspective Theorem

The orderings of regions determined by 1-dimensional subsections from an outside region to its complement form a partial ordering of all regions.

Consider two 1-dimensional subsections between outside region R₀ and region R₁. Boundary B separates R₀ and R₁ in one subsection iff it does in the other. Therefore a region ordering set up in both subsections must be the same in both subsections.

Construction Algorithm

Given a finite linear space, the Constructibility Theorem proves that there exists a set of isomorphic linear surfaces. However, the Constructibility Theorem does not provide an algorithm for producing sample isomorphic linear surfaces. Here I will present such an algorithm. The input to the algorithm is a set of linear surfaces B in a space of dimension n, and a set of regions R isomorphic to a linear section. The output is a linear surface dividing the regions in R. Choose a linear surface b₀ and n noncoincidental points p₀, p₁, ... p_n-1 on b₀. Let f map each linear surface b to a point p with coordinates equal to the lengths of the segments perpendicular to b₀ from b to p₀, p₁, ... p_n-1. I claim that f maps linear surfaces through the same point to points on a linear surface. Thus f determines mapping g from points to linear surfaces. Since b₀ provides an orientation, two linear surfaces can be opposite or on the same side of a point. Let Q be the intersection points of each n-tuple from B, and D be the linear surfaces mapped to from Q by g. D forms a finite linear space with regions corresponding to sections in B. To find a linear surface dividing the regions in R, find which side of R each point in Q is on. Use those sidednesses to determine a region x in D. Choose a point y in x. Apply the inverse of f to y to obtain a linear surface dividing the regions in R.

I must prove that the map g from point to linear surface is well defined.

Consider a linear surface b through point p that f maps to coordinates c₀, c₁, ... c_n-1. Since b goes through p, one coordinate c_i depends on the other coordinates. If every coordinate except c_i and one other c_j is held fixed, then by similar triangles, c_i = dc_j + e, for some scalars d and e. Thus, the dependence of c_i upon the other coordinates is the affine composition of affine functions. Therefore, the coordinates lie on a linear surface.

Implications of this algorithm for abstract linear spaces include that every linear space of the same number of boundaries has the same number of sections, and that the notion of sidedness of n-tuples of boundaries wrt boundaries is well defined.

Section Space Theorem

If space S₀ⁿ is linear, then there exists linear space S₁ⁿ, unique up to isomorphism, with boundaries corresponding to n-tuples of boundaries from S₀ⁿ and regions corresponding to sections of S₀ⁿ.

The proof follows from the algorithm above.

Procedural Proof

The proof of the Independent Boundary Theorem in a previous post is incorrect because I failed to establish an isomorphism before applying the Antisection Theorem. To make the Independent Boundary Theorem proof more precise, I will present it as a method called extend in a class called Space. Other methods left undefined are the linear function that returns whether the given Space is linear, section and antisection that work like the Section Theorem and Antisection Theorem, and the take function. The take function converts regions from one Space to regions on the same side of shared boundaries in another Space. If both the containing Space and the given Space have the same boundaries, then take finds isomorphic regions; otherwise, take finds super-regions or sub-regions.
Space Space::extend(
  const Space &S0,
  const Space &S1,
  const int b0,
  const int b1) const {
  assert(linear());
  assert(S0.linear());
  assert(S1.linear());
  assert(boundaries()==S0.boundaries());
  assert(boundaries()==S1.boundaries());
  assert(dimension()==S0.dimension()+1);
  assert(dimension()==S1.dimension()+1);
  assert(take(S0.regions(),S0).size()==S0.regions().size());
  assert(take(S1.regions(),S1).size()==S1.regions().size());
  assert(!boundaries().contains(b0));
  assert(!boundaries().contains(b1));
  Space S2 = antisection(take(S0.regions(),S0),b0); // n2=n
  if (dimension()==1) {
    return S2.antisection(S2.take(S1.regions(),S1).choose(),b1);}
  Space S3 = subsection(S0,S1); // n3=n-1+n-1-n=n-2
  Space S4 = S1.antisection(S1.take(S3.regions(),S3),b0); // n4=n-1
  Space S5 = S2.antisection(S2.take(S4.regions(),S4),b1); // n5=n
  set<int> B0 = S5.boundaries().erase(b1);
  set<int> B1 = S5.boundaries().erase(b0);
  assert(S5.subspace(B0)==antisection(take(S0.regions(),S0),b0));
  assert(S5.subspace(B1)==antisection(take(S1.regions(),S1),b1));
  assert(S5.linear());
  return S5;}
Space Space::subsection(
  const Space &S0,
  const Space &S1) const {
  assert(linear());
  assert(S0.linear());
  assert(S1.linear()):
  assert(boundaries()==S0.boundaries());
  assert(boundaries()==S1.boundaries());
  int n = dimension();
  int n0 = S0.dimension();
  int n1 = S1.dimension();
  assert(n0+n1-n>=0);
  if (boundaries().size()==0) {
    return Space(n0+n1-n);}
  int b = boundaries().choose();
  set<int> B = boundaries().erase(b);
  set<int> R = attached(b);
  Space S2 = subspace(B); // n2=n
  Space S3 = S0.subspace(B); // n3=n0
  Space S4 = S1.subspace(B); // n4=n1
  Space S5 = S2.section(S2.take(R,*this)); // n5=n-1
  Space S6 = S2.subsection(S3,S4); // n6=n0+n1-n
  Space S7 = S2.subsection(S5,S6); // n7=n-1+n0+n1-n-n=n0+n1-n-1
  Space S8 = S6.antisection(S6.take(S7.regions(),S7),b); // n8=n0+n1-n
  assert(S8.dimension()==n0+n1-n);
  assert(take(S0.regions(),S0).contains(take(S8.regions(),S8)));
  assert(take(S1.regions(),S1).contains(take(S8.regions(),S8)));
  assert(S8.linear());
  return S8;}

Outsidedness

My proof of the Constructibility Theorem in a previous post has a flaw. A base region of a simplex is the inside with one boundary reversed. The Fourth Constructibility Lemma is false as stated because the regions may be in the base regions of the constructed simplex. Thus I need a corollary of the Simplex Theorem proving a space with a boundary dividing all base regions of a simplex is not linear. The proof of the Simplex Corollary will require the Migration Theorem, and the Outside Neighbor Theorem. The Migration Theorem requires the Corner Theorem.

MIGRATION

Define a neighbor of region R wrt boundary b as a region separated by and only by b from R. Regions R₀ and R₁ are neighbors iff they are neighbors wrt some boundary. A region R and boundary b are attached iff R has a neighbor wrt b. The corners of a set of boundaries B are the regions attached to every boundary in B. Region R₁ is the opposite of region R₀ iff R₁ is separated from R₀ by and only by boundaries attached to R₀. Spaces S₀ⁿ and S₁ⁿ are migrations of each other iff they are identical except for mutually opposite regions R₀ and R₁, such that R₀ is nonempty in and only in S₀ⁿ, and R₁ is nonempty in and only in S₁ⁿ.

CORNER THEOREM

A space Sⁿ with m boundaries is linear iff for each set of l boundaries B from Sⁿ, the number of corners of B is 2^lf(n-l,m-l).

The sections of Sⁿ with B removed by each boundary in B produce a space corresponding to f(n-l,m-l) regions in Sⁿ with B removed. The boundaries of B divide each of those regions into 2^l regions. Thus the only if part is proved. For the if part, proceed by induction on number of boundaries. The correct numbers of corners are preserved when removing a boundary, and the section by the removed boundary has the correct numbers of corners, so the space without the boundary removed is linear by the Antisection Theorem. To complete the proof, note that the empty space has the correct numbers of corners and is linear.

MIGRATION THEOREM

If S₀ⁿ and S₁ⁿ are migrations of each other, then S₀ⁿ is linear iff S₁ⁿ is linear.

The corners of a set of boundaries B are the same in S₀ⁿ and S₁ⁿ except for R₀, R₁, and neighbor regions of R₀ and R₁. R₀ and R₁ replace each other, and their neighbors replace each other. Thus the theorem is proved by the Corner Theorem.

OUTSIDE

A region is inside iff it is a subregion of the inside of a simplex subspace. A region that is not inside is outside. Intuitively, think of outside regions as peripheral regions with infinite extent. An outside neighbor of a region is a neighbor that is outside.

OUTSIDE NEIGHBOR THEOREM

In a space of dimension n, the number of outside neighbors of any region is not more than n+1.

A simplex has only n+1 outside neighbors, and adding a boundary does not increase the number of outside neighbors of the subregions.

SIMPLEX COROLLARY

If b divides the base regions of a simplex in linear space Sⁿ, then Sⁿ extended by b is not linear.

By definition of linear, I can consider the simplex subspace. Assume Sⁿ extended by b is linear. Consider the section of Sⁿ by b. If b does not divide the inside of Sⁿ, b divides the vertex regions of the migration of Sⁿ. This contradicts the Simplex Theorem, so b does divide the inside of Sⁿ. In the section of Sⁿ by b, because of the Outside Neighbor Theorem, one of the regions, say R opposite boundary b₀ from the inside, is inside in the section. If R is a simplex, its opposite corresponds to another one of the base regions in Sⁿ, and is not empty. This contradiction implies that R is not a simplex, and has more than n neighbors. Then the section by b₀ of Sⁿ with b₀ removed has base regions divided by b. This contradicts induction on dimension. To complete the proof, note that in a 1 dimensional space, no boundary divides the base regions of a simplex because no boundary divides more than 1 region.

A Little Language

Here I will present the command interface to a program for creating and manipulating objects displayed through computer graphics. Internally, objects are represented as sidedness spaces together with boundaries attached to super-regions representing 2d facets.

In the following, Ca Cb Cc ... represent keys pressed with the control key. F1 F2 ... Fn represent the function keys along the top of the keyboard. Except at the start of a statement, --- represents a subexpression to be evaluated before the containing expression. +++ represents an expression to be parsed but not evaluated. ___ represents a string. abc represents a name. dfe represents a file, directory filename extension. 123 represents an identifier. 012 represents a number. 01 represents a boolean. ... represents repetition. Statements introducing subsequent statements begin with ---. Statements describing commands begin with the command as entered with optional whitespace. The same command may have multiple forms, in which case the statement describing the command begins with each of the forms. For an example of a command with three forms, see the O command.

--- Create objects or parts of objects

O< 012 >
O< 012 012 >
O< < 012 012 > ... > Create space, polytope, or overlap, topologically different from selected.
x Create plane perpendicular to x axis.
y Create plane perpendicular to y axis.
z Create plane perpendicular to z axis.
c Create inflate select object from selected boundaries.
a Add selected facets.
s Subtract selected facets.
d Divide selected facets by new random boundaries.
b Divide selected facets by selected boundaries.
i Create union of selected objects.
j Create intersection of selected objects.
k Create symmetric difference of selected objects.

--- Drag objects or parts of objects to transform them

T Tweak selected.
t Translate selected by drag amount.
R Rotate selected about axis, through pierce point perpendicular to picture plane, by drag amount.
r Rotate selected about axis, through pierce point parallel to picture plane, by drag amount.
X Stretch selected in x dimension by drag amount.
Y Stretch selected in y dimension by drag amount.
Z Scale selected by drag amount.

--- Remove objects or parts of objects

C Remove selected boundaries from selected objects.
m Unshare selected boundaries from selected objects.
o Where possible without changing appearance, combine selected facets, remove selected boundaries, reindex selected objects.

--- Specify objects, object parts, or transformations with entered numbers or identifiers

,{ --- }
,{ --- ... }
,< < 01 ... > ... > Create and select boundaries from sidedness.
.{ --- }
.{ --- ... }
.< 012 ... > Create and select boundary from numbers.
;{ --- }
;{ --- ... }
;< < 123 ... > ... > Create and select object from boundary identifiers.
#{ --- }
#{ --- ... }
#< 012 ... > Transform selected.

--- Return displayed state

@{ --- }
@{ --- ... }
@< 012 ... > Return info about point containers.
${ --- }
${ --- ... }
$< 012 ... > Return info about line pierces.
%{ --- }
%{ --- ... }
%< 012 ... > Return info about plane divides.
W Return selected metrics.
w Return selected identifiers.

--- Select objects or object parts for subsequent commands to operate on

:{ --- }
:{ --- ... }
:< < 123 ... > ... > Set persistent selection from identifiers.
e Toggle whether selected is in persistent selection.
n Deselect from persistent.
u Select to persistent.

Fn Modify selection.

--- Modify behavior of subsequent commands

0{ --- --- }
0< 012 012 >
0{ --- }
0< 012 >
0 Replace mode mask for next command that consumes, push global set and clear mode masks, or pop global masks.
1 Set vertex bit 0x001 in mode mask for next command that consumes.
2 Set edge bit 0x002 in mode mask for next command that consumes.
3 Set face bit 0x004 in mode mask for next command that consumes.
4 Set region bit 0x008 in mode mask for next command that consumes.
5 Set super-region bit 0x010 in mode mask for next command that consumes.
6 Set boundary bit 0x020 in mode mask for next command that consumes.
7 Set object bit 0x040 in mode mask for next command that consumes.
8 Set temporary bit 0x080 in mode mask for next command that consumes.
9 Set tentative bit 0x100 in mode mask for next command that consumes.
Ci Add Cx overload bit 0x200 to mode mask for next command that consumes.
Cj Add Cy overload bit 0x400 to mode mask for next command that consumes.
Ck Add Cz overload bit 0x800 to mode mask for next command that consumes.

--- Ignore except when overloaded

_ Do nothing except consume mode mask.
Cx Do nothing unless overloaded, as by command with Ci mode mask. Issued by Console in mouse click glut callback.
Cy Do nothing unless overloaded, as by command with Cj mode mask. Issued by Console in mouse move glut callback.
Cz Do nothing unless overloaded, as by command with Ck mode mask. Issued by Console in mouse release glut callback.

--- Imply vectors used by subsequent commands

`{ --- }
`{ ---  ... }
`< 012 ... > Find current pierce point from picture plane coordinate, updating temporary selection, coordinate, valid. Issued by Console before Cx.
~{ --- }
~{ --- ... }
~< 012 ... > Find drag point from picture plane coordinate. Issued by Console before Cy and Cz.
Cm{ --- }
Cm( abc ) Change current Layer, updating pierce point, temporary selection, valid.
Cn{ --- }
Cn( abc ) Change current Layer, updating coordinate, valid.
Cu{ --- }
Cu{ --- ... }
Cu< 012 ... > Change current coordinate, updating valid, pierce point, temporary selection.
Cv{ --- }
Cv{ --- ... }
Cv< 012 ... > Change current pierce point, updating temporary selection, coordinate, valid.
Cw{ --- }
Cw{ --- ... }
Cw< 012 ... > Change current drag point.

--- Layer coordinates and mappings onto surfaces

Cl{ --- }
Cl( abc ) Return Layer from Texture, selected objects and facets, poke and scratch.
Co{ --- }
Co{ --- ... }
Co( abc ... ) Display ordered list of Layers.
Cp{ --- }
Cp{ --- ... }
Cp( abc ... ) Restrict Layers according to prominence until they do not overlap.
Cq{ --- }
Cq{ --- ... }
Cq( abc ... ) Extend Layers to their union.
Cr{ --- }
Cr{ --- ... }
Cr( abc ... ) Restrict Layers to their intersection.
Cs{ --- }
Cs{ --- ... }
Cs< 012 ... >
Cs Return ordered list of Layers valid at optional line or current pierce point.
Ct{ --- }
Ct( dfe ) Load and return Texture.

--- Start heuristic to automatically change displayed state

p{ --- }
p( dfe )  Return Heuristic loaded from library.
q{ --- ... }
q( abc ... ) Start Heuristic on selected.

--- Save and restore displayed state

H Redo change to subject.
h Undo change to subject.
L Go to next history branch.
l Go to last history branch.
F{ --- }
F( dfe ) Read subject from file.
f{ --- }
f( dfe ) Save subject to file.
G{ --- }
G( dfe ) Read history from file.
g{ --- }
g( dfe ) Save history to file.

--- Build expressions

" Return text with prepended length.
'{ --- }
'[___] Return text up to terminator.
( abc ... ) Return names.
< 012 ... > Return numbers.
[___] Return text.
{ +++ ... } Return expressions.
+{ --- --- } Add values.
-{ --- --- } Subtract values.
*{ --- --- } Multiply values.
/{ --- --- } Divide values.
\{ --- --- } Return modulus of values.
&{ --- --- } Return and of values.
|{ --- --- } Return or of values.
^{ --- --- } Return exclusive or of values
D{ --- ... } Execute subexpressions, but discard results.
E{ --- ... } Execute subexpressions, and return results in structure.
P Pop from before current frame.
Q{ --- ... } Return elements of subexpressions as multiple results.
S{ --- }
S( abc )
S{ --- --- }
S( abc 012 )
S{ --- --- --- }
S( abc 012 012 )
S{ --- --- --- --- }
S( abc 012 012 abc ) Return size, element, substructure, or copy with range replaced.
Cd{ --- }
Cd( abc ) Return deep copy.

--- Control variables and flow

M{ --- }
M< 012 > Reenter number of nesting levels.
N{ --- }
N< 012 > Break out number of nesting levels.
={ --- --- }
=( abc --- ) Assign value to name.
U{ --- }
U( abc ) Unassign name.
V{ --- }
V( abc ) Return named value.
v{ --- }
v( abc ) Execute named command.

--- Access program state

A Return kernel reference values.
B{ --- }
B( abc ) Set kernel reference values or value chosen by type.
Ce Return new empty Command.

--- Open stream for input and output

!{ --- }
![___] Return Source to pipe commands to Value and from string.
?{ --- }
?[___] Return Source to pipe commands to and from socket.
I{ --- --- }
I( dfe dfe ) Return Source to pipe commands to and from files.
J{ --- }
J[___] Return Source to pipe commands to and from c code.
K{ --- }
K[___] Return Source to pipe commands to and from shell.

--- Replace commands executed by syntax pattern in syntax table

Ca{ --- --- --- }
Ca( abc [___] [___] ) Change command string executed after command associated with pattern in Syntax.
Cb{ --- --- --- }
Cb( abc [___] [___] ) Change command string executed before command associated with pattern in Syntax.
Cc{ --- --- --- }
Cc( abc [___] [___] )
Cc{ --- --- --- --- }
Cc( abc [___] chr 012 ) Change command string or command and mode associated with pattern in Syntax.
Cf{ --- --- --- }

--- Copy and alias portions of value assignments

Cf( abc ( abc ... ) abc )
Cf( abc abc ( abc ... ) ) Copy listed, or all except listed, names from Language.
Cg{ --- --- --- }
Cg( abc ( abc ... ) abc )
Cg( abc abc ( abc ... ) ) Share listed, or all except listed, names with Language (symmetric alias).
Ch{ --- --- --- }
Ch( abc ( abc ... ) abc )
Ch( abc abc ( abc ... ) ) Observe listed, or all except listed, names from Language (asymmetric alias).