# 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 *C*_{1}, ... C_{k}, C* of the tesselation holds: if the intersection $\bigcap{k\atop {i=1}}C_{i}$ of all *C*_{i} is nonempty and each *C*_{i} has nonempty intersection with *C**, then the intersection *$C*\cap\bigcap{k\atop {i=1}}C*_{i}$ 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