TILINGS WITH THE NEIGHBORHOOD PROPERTY

VOL. 19 NO. (1996) 33-38

TILINGS WITH THE NEIGHBORHOOD PROPERTY

LINDA S. FOSNAUGH Divisionof Mathematics MidwestemStateUniversity

3410Taft Boulevard WichitaFalls,TX76308-2099

and

EARL S.KRAMER

Department

ofMathematics

Universityof Nebraska Lincoln, Nebraska 68588-0323

(Received

January

11,

1994)

ABSTRACT. Theneighborhood

N(T)

ofatile

T

is theset of all tiles whichmeet

T

inatleast one point. If for each tile

T

thereis adifferenttile

T1

^suchthat

N(T) N(T1)

^{then we}saythe tiling has the neighborhood property

(NEBP).

Cm:inbaum and Shepard conjecture that it is impossible to have a monohedral tiling of the plane such that every tile

T

has two different tiles TI,T2 with

N(T) N(T) N(T:z).

If all tiles are convexweshow thisconjectureistrueby characterizingthe convexplane tilingswithNEBP. More preciselyweprovethataconvexplane tilingwithNEBPhasonly triangular tiles and eachtilehas a3-valentvertex. Removing 3-valentvertices and theincidentedges from suchatilingyieldsanedge-to-edge planartriangulation. Conversely,given anyedge-to-edge planar triangulation followed byinsertion ofa vertexand three edges that triangulate each triangle yieldsa convexplane tilingwithNEBP. Weexhibit aninfinitefamily of nonconvex monohedralplanetilings with NEBP. We brieflydiscusstilings of

R

³withNEBPand exhibitamonohedral tetrahedraltiling of

R

³

withNEBP.

KEY

WORDS AND PHRASES. Tiling andneighborhood.

1991AMSSUBJECT CLASSIFICATION CODES. 05and52.

1. INTRODUCTION.

A plane tilingdenotedby 7"is acountable family of closedsetswhichcover theplanewithoutgaps oroverlaps. Tilescanintersect alongtheirboundaries but interiorsaredisjoint. Weassume allofour tiles are

(closed)

topologicaldisks.

A

tiling

T

is convex if all tiles areconvex, andmonohedralifevery tile in

T

is congruenttoa fixed tile

T,

which iscalledtheprototileof7". Theneighborhood

N(T),

^{in a} gi,;,en tiling,isthesetof tiles consisting of

T

andalltileswhichmeet

T

in atleast onepoint. Ifforeach tile

T1

^{there isa}different tile

T2

^{such that}

N(T1) N(T2),

thenwecallthistheneighborhoodproperty

(NEBP).

Ifour tiles are polygonsthen atiling is edge-to-edge ifthe intersection ofevery pair of nondisjointtilesis eithera vertex or anedge. Cm:inbaum andShephard

[5]

posedthefollowingproblem:

Show that there is nomonohedral tiling, in whichthe prototileis apolygonaldisk, such thatfor tile

T

thereexist two other tiles

T

^and

T.

^suchthat

N(T) N(T N(T2).

We showthis is trueif thetiles areconvexby characterizingtheconvexplanetilings with theNEBP.

2. CONVEX PLANE TILINGS.

In

R

acone of supportto aclosedset

A

atapointp on itsboundaryisthe intersection of all closed halfspaceswhichcontain

A

andwhichcontain p intheirboundary hyperplanes. Let Sbeaconvexset.

ApointzinS iscalledan extremepoint ofS ifthereexists no nondegeneratelinesegment inS that contains z in itsrelativeinterior. ThesetofextremepointsofSiscalledtheprofile of

S.

It^{is a}theorem thatifSis acompact convex subset of

R ’,

thenSistheconvexhull of its profile. If7⁹isa setof points thenwelet^cony79denote the convex hull of79.

Herewe assumethatour tiles are convexand (asstated previously)topological disks. Let

T

^and

T2

be different tiles forwhich

N(T) N(T).

They clearlymeetand sincetheyare convextheycan be separated byastraight lineL. Weassumethat

L

is orientedtobe the z-axis,and

T

^isabovethe z-axis.

Let#be a point of

T1

^{that isat maximumdistancefrom}the z-axis. Such_aftexistssince

T1

is compact.

If anondegenerateline segment

L’

in

T1

^containedftin its relative interioror ifthesupportingcone_{at ft} were ahalf-space,then therewould beatile

Ts

^touching

T1

^atftwhere

T3 N(T2).

^{Thus thepoint}ft is an extremepointof

T1

^andthe supporting_{cone at ft}isnota

half-space. Let L1

^and

L2

^betworays

frrmingthe supportcone_{at ft.} Itisclear that thesetwo rays

L

and

L

2 must intersectL. Also,the convexityof ourtilesimplies thatatleast three tilesmeet at ft.

Suppose

Ts

^and

T4

^meet

T1

at ft and are separated from

T1

^bylines

Ls

^{and /-,4,} respectively.

Arguingsymmetricallyfor

T,

therewould bea anda whichwouldmeet

T2

^{atan extremepoint}

ft’,

andwhich are separated from

T ^byL

^and

L.

^{It isthen elementaryto establishthatthe lines}

L,

L3,

L

^intersectinacommon pointP3, and P3^E

T1

^N

T

^f

T3

^N

.

Analogously,

L,

L4,

L

^intersect

in a common_Now

_{p,

point

_P4ft}

P4,

_{c T,}

and P4

_T

⁵_is

T T

convex, and^N

T4 T

^N

.

^isbounded by L3,L4,

L,

hence

T1

^isthetriangle with verticesft,P3 and P4. Analogously,

T2

^isatrianglewith vertices

ft’,

_{P3 and P4.} Clearly

T

and

T’

share an edge.

Suppose

another tile

T5

^met

T

^atft. Then

T5

^couldmeet

T

^onlyat/93or P4. Butthisisdearly impossible because of thelocationof

T, T4

and the fact that

Ts

^isconvex.

^We

^haveproven:

PROPOSITION2.1. Let

7"

bea convexplanetilingwithNEBP. Thenthe tilesof 7"aretriangles.

If

T : ^T’

^and

^{N(T) N(T’),}

^then

^T

^and

^T’

^{share anedge. Inaddition,exactly}three tilesmeetat vertex

ft(ft’) ofT(T’)

^{whichis not onthe}sharededge.

PROPOSITION2.2. Thetilingisedge-to-edge.

PROOF. Let

ea

^{be theedge of}

T3

^andelbetheedge of

T1

which are both contained intheline

Ls

that separates

T3

^and

T.

^Theproofof Proposition2.1 shows that

e

^C

ca.

^If

N(T:;) N(T),

^then

es e

by Proposition2.1.

IfN(Tz) - ^N(T),

^let

^T3

^playthe role of

T

ⁱⁿProposition2.1 toget that

es

^C

e.

^Thus

es

el.

A

symmetric argumentshowsthattheedge of

T

^andthatof

T4

^thatliealong

L4

must coincide. Theresult followssince

T

^isanarbitrary tile.

PROPOSITION 2.3. Let 7" be a convex planetilingwithNEBP. Then each tile(which is a triangle)has exactlyone 3-valentvertexand theothertwoverticesare atleast 6-valent. Further, the edge opposite the3-valentvertexinatile issharedbytwotiles whoseneighborhoodsareequal.

PROOF.

By

Proposition2.1 thevalency ofvertex_#in

T

^{is 3andsince}tiles are convex,thethird vertex ofT3, besides_P3andft,mustbeatastrictly greaterdistancefrom

L

than_ft. Letthisvertexbe P5 and

let

theanalogousadditionalvertexof

,

besides P3and

ft’,

be

p. Note

that

T3 conv{ft,

P3,P5

}

and

conv{ft’,

P3,

I ^}, T4 ^conv{ft,

^P4,

}

and

conv{ft’,

P4,

P ^}.

^{But thereis}no tile with vertices_P3,P,

1

^{since sucha tilewouldhaveno vertexofvalencythree. HencethevalencyofP3,and}

analogously

P4,mustbeatleast6. The finalstatementofourresultisthenimmediate.

Define aplanetriangulatton

refinements

^asfollows Beginwithanyedge-to-edgetiling of theplane bytriangles. InsertapointPT ^{intheinterior}of each triangleTanddrawanedgefromPT^toeach of the verticesofT. Dothisforeachof the tiles in theoriginalplane triangulation.

TItEOREM 2.1. A convex plane tiling with NEBP is equivalent to a plane triangulation refinement.

PROOF. A planetriangulationrefinement iseasily checkedtobeaconvexplanetilingwithNEBP.

Conversely, letTbe a convexplane tilingwithNEBP. Deleteall vertices that areinitially 3-valentand the incident edges.

By

Proposition2.3 everytilein7"isremovedbythis process. What remains isan edge-to-edge triangulation of the plane Using the discarded 3-valent vertices as the

pr’s

gives a refinementthatrecreates7". Ourresultisclear.

PROPOSITION2.4. Foranyfixed positive integer k thereis aconvexplane tilingwithNEBP usingexactlykdifferent tileshapes

PROOF. Beginwith anedge-to-edge tilingof theplanewithequilateraltriangles. Fork 1 we produce a refinement by choosing

Pr

^{tobe the centroid ofeachtriangle. For k 2 weproduce a}

refinementbychoosingPr^onthelinethroughthe centroidand perpendiculartothe baseof

T,

butPr^is

not set atthe centroid. Fork 3choosePT ^{sothreedistincttrianglestile}T. Clearly,by choosing the placement of the

pr’s

we can produce a refinementwith any given positive number ofk distinct tile shapes.

3. CONVEX MONOHEDRAL PLANE TILINGS WITH NEBP.

Weare nowinpositiontocompletelycharacterizethe monohedral convexplanetilingswithNEBP.

THEOREM3.1. Thereisauniquemonohedralconvexplane tiling 7"withNEBP.

PROOF.

We

needasimple factthat iseasytoverify. Let

T

beatriangle and letT1,

T2

^and

T3

^be

threetrianglesthattile

T

edge-to-edge. If

T1

^{iscongruenttoTgthen}

T3

^{is an}isosceles triangle. If all three tilesareequal,theneachisthetrianglewithangles30

,

^{30 and120}

.

^{Itis now}clear that removal ofall 3-valent vertices from7" along withincidentedgesproduces anedge-to-edge tilingof theplane with equilateral triangles. Such atiling is unique, so our tiling

T

is obviously unique. Thistiling is exhibitedinFigure3.1.

Figure3 1.

The automorphism group ofatiling 7- isthe setofisometricsthat preservethetiling Suchagroup partitionsthe tiles intotransitivityclasses where anytwotileswithinaclasscanbemappedtoeachother viasomeautomorphism.

A

tiling 7"is isohedral if there isonlyonetransitivityclass. Theplaneisohedral tilings are

completely

^known (see [3]or

[4])

and amongthe isohedral plane tilings onlythe tilingof

Figure

^3.1has NEBP. Thuswehave:

PROPOSITION3.1. Thereisaunique isohedralplane tilingwithNEBP

Notethat Theorem3.1 and Proposition^3.1 provethe Grnbaum and Shephard conjecture(statedinthe introduction)for plane tilings^{when the}tilingsareeither convex or isohedral.

4. NONCONVEX PLANE TILINGS WITH NEBP.

Onesimpleexampleofa nonconvexplanetiling withNEBPisgivenasfollows: Withcenter

C

on a straight line L draw circles with varyingradiithat become arbitrarily large Thetiles arethe simply- connected regions. The pair oftiles sharing the same two edges lying along L will have the same neighborhood.

WenowproducemonohedralnonconvexplanetilingwithNEBP Figure⁴ shows howto"dent in"theedges ofeachtriangleinthe tiling of Figure3.1 so thatthetilingis stillmonohedral.

Figure4.1.

Thefollowinglemmais aneasy exercise and thesubsequentproposition isimmediate.

LEMMA

4.1. If the denting process isappliedtoFigure 3.1 ^toproduceamonohedralpolygonal nonconvexplane tilingwith

NEBP,

^{then each}tilehasanoddnumberof sides.

PROPOSITION4.1. Foreachoddinteger^k

>

3, thereisamonohedralplanetilingwithNEBP usingtiles with k sides.

Onehastowonderhere whether all monohedralplanetilings^withNEBParise fromFigure3.1bya suitable denting process. Fromtheproofof Proposition2.4andthe "denting"procedurewehave:

THEOREM 4.1. Forany fixedpositive integer kthere isa nonconvexplane tiling withNEBP usingexactlykdifferenttileshapes.

5. SOME TILINGS OF

R

³WITH NEBP.

Wecanextend atilingof theplanetoatiling

of/3

byanaturalliftingprocess (mentionedtousby B. Cjrnbaum). Let

T

be aplane tiling

(taken

tobe in the xy-coordinateplane) and dafixedpositive distance. Define

L(’T, d)

^asfollows: for each

T

in

7",

construct aprismwithbase

T

and heightd. This producesaslab and nowwestack such slabs

(face-to-face)

^to

fill/3.

Ournextresultiseasytoverify.

PROPOSITION5.1. Let

T

be aplane tilingwithNEBP. Then

L(’T, d)

^{is a}tiling of

R

³with NEBP.

From Proposition^4.1and Proposition 5.1,weimmediatelyhave:

COROLLARY5.1. Foreachodd positive integer k

>_

5 there isamonohedraltilingof

R

³with NEBP wherethe tileshaveexactlyk faces.

We generalize the refinementprocessdescribedpriortoTheorem 2.1. Begin withaface-to-face tiling

"T

or

R

³usingtetrahedral ^and/orhexahedrawithtriangular^faces. Insertapoint

Pr

ⁱⁿthe interior ofeach tile

T.

Clearly

T

canbe subdivided into tetrahedra thataredeterminedby

Pr

^{and eachface of}

T.

Dothis for each

T

in7"togeta refinementof the original face-to-face tiling. The following theorems is easytoverify:

THEOREM5.1. The refinement ofaface-to-facetiling of

R

³using tetrahedra^and/orhexadehra with triangularfaces,is a tetrahedraltilingof

3

withNEBP.

A tetrahedron is isosceles if opposite edges are equal. An isosceles tetrahedron clearly has congruent faces. Also, a tetrahedron is isosceles iffthe medians are equal, e., iff the centroid is equidistant from theverticesof thetetrahedron.

THEOREM 5.2. If thereis amonohedralface-to-face tiling of

R

³with isosceles tetrahedra, then thereis amonohedral face-to-face tiling with tetrahedra of

R

³withNEBP.

PROOF. The medians of the isosceles tetrahedra are equaland the faces are congruent. Ifwe choose

PT

^{tobe thecentroidofagiven}tetrahedron,thenthe resulting tetrahedrainthe refinementwillbe congruent. OurresultfollowsbyTheorem5.1.

The isoscelestetrahedron

To

^{with side}lengths2, 2,

V/’, V/-, v/’,

^and

v/,

^{tiles E3}face-to-face (see

[2]).

In Figure5.1 three copies

ofT0

^{areshowntotile}

Figure5.1.

aprism. Thisprismcaneasily be stacked and translatedtoproduceaface-to-face tiling of

R

^susing

To.

Using Theorem5.2the followingisthen clear:

COROLLARY5.2. Thereis amonohedraltetrahedraltiling^of

R

^swithNEBP.

6. FINAL REMARKS.

One question posedearlieriswhether all monohedralplane tilingswithNEBParisefrom Figure3.1 bya suitabledenting process. Another natural question is whether there is a succinct characterizationof convextilingsof

R

³withNEBPasthere wasforconvexplane tilingswithNEBP.

ACKNOWLEDGEMENT.

Theorem 5.1.

The authors acknowledge Elisabeth Arnold who helped generalize

REFERENCES

1.

ALTSHILLER-COURT, N.,

^ModernPureandSolid

Geometry,

ChelseaPublishing

Company,

New York, 1964.

2.

GOLDBERG, M.,

Three infinite familiesoftetrahedral space-fillers,

J.

Comb. TheoryA16 (1974),348-354.

3. GOLDBERG,

M.,

Onthe space-fillinghexahedra,Geometriae Dedicata 6(1977),99-108.

4.

GRtJNBAUM,

B.and

SHEPHARD,

G.C.,Isohedral tilings of theplane by polygons, Comment.Math.Helvet.53

(1978),

^542-571.

5.

GRI3NBAUM,

B.andSHEPHARD, G.C., Tilings andPatterns, W.H. Freemanand

Company,

New York, 1987.

6.

LAY,

S., Convex SetsandTheirApplications,JohnWiley^and

Sons,

New York, 1982.

7.

SENEcHAL, M.,

Whichtetrahedra fill

space?,

MathematicsMagazine54(1981),^227-243.