Wednesday, December 24, 2014


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.

Thursday, November 6, 2014


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 R0 and R1 are complementary, and R0 is inside. By the Subsection Theorem (unproven), there is a 1-dimensional subsection L with regions isomorphic to R0 and R1. Since R0 is inside, the number of boundary reversals between R0 and R1 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 R0 in the polytope with neighbor R1 not in the polytope separated by boundary B, find whether the perspective region is on the same side of B as R1, and xor that with nearness of R0. 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 R0 and R1. 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 R0 and region R1. Boundary B separates R0 and R1 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.

Friday, September 26, 2014

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 b0 and n noncoincidental points p0, p1, ... pn-1 on b0. Let f map each linear surface b to a point p with coordinates equal to the lengths of the segments perpendicular to b0 from b to p0, p1, ... pn-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 b0 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 c0, c1, ... cn-1. Since b goes through p, one coordinate ci depends on the other coordinates. If every coordinate except ci and one other cj is held fixed, then by similar triangles, ci = dcj + e, for some scalars d and e. Thus, the dependence of ci 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 S0n is linear, then there exists linear space S1n, unique up to isomorphism, with boundaries corresponding to n-tuples of boundaries from S0n and regions corresponding to sections of S0n.

The proof follows from the algorithm above.

Thursday, September 11, 2014

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 {
  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);
  return S5;}
Space Space::subsection(
  const Space &S0,
  const Space &S1) const {
  int n = dimension();
  int n0 = S0.dimension();
  int n1 = S1.dimension();
  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
  return S8;}

Friday, August 29, 2014


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.


Define a neighbor of region R wrt boundary b as a region separated by and only by b from R. Regions R0 and R1 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 R1 is the opposite of region R0 iff R1 is separated from R0 by and only by boundaries attached to R0. Spaces S0n and S1n are migrations of each other iff they are identical except for mutually opposite regions R0 and R1, such that R0 is nonempty in and only in S0n, and R1 is nonempty in and only in S1n.


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

The sections of Sn with B removed by each boundary in B produce a space corresponding to f(n-l,m-l) regions in Sn with B removed. The boundaries of B divide each of those regions into 2l 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.


If S0n and S1n are migrations of each other, then S0n is linear iff S1n is linear.

The corners of a set of boundaries B are the same in S0n and S1n except for R0, R1, and neighbor regions of R0 and R1. R0 and R1 replace each other, and their neighbors replace each other. Thus the theorem is proved by the Corner Theorem.


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.


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.


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

By definition of linear, I can consider the simplex subspace. Assume Sn extended by b is linear. Consider the section of Sn by b. If b does not divide the inside of Sn, b divides the vertex regions of the migration of Sn. This contradicts the Simplex Theorem, so b does divide the inside of Sn. In the section of Sn by b, because of the Outside Neighbor Theorem, one of the regions, say R opposite boundary b0 from the inside, is inside in the section. If R is a simplex, its opposite corresponds to another one of the base regions in Sn, and is not empty. This contradiction implies that R is not a simplex, and has more than n neighbors. Then the section by b0 of Sn with b0 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.

Wednesday, January 22, 2014

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).