On strongly normal tesselations

Peter Braß
Institut für Informatik
Freie Universität Berlin
Takustr. 9, D-14195 Berlin
email: brass@inf.fu-berlin.de

Report B 99-06
April 1999

A tesselation C is called strongly normal (topological discs with intersections that are either empty or connected) and for any subset of cells C1, ... Ck, C* of the tesselation holds: if the intersection $\bigcap{k\atop {i=1}}Ci$ of all Ci is nonempty and each Ci has nonempty intersection with C*, then the intersection $C*\cap\bigcap{k\atop {i=1}}Ci$ with C* is nonempty. This concept was introduced for polygonal or polyhedral cells in a recent paper by Saha and Rosenfeld, where they proved that it is equivalent to the topological property that any cell together with any set of neighboring cells forms a simply connected set. Answering a question from their paper, it is shown here that at least in the plane the cells need not be convex polygons , but can be arbitrary topological discs. Also the property is already implied if all collections of three cells have this property, giving a simpler characterization and a connection to Helly-type theorems.

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-99-06.ps.gz