steve's post went to another list (probably by accident). the reply
may be of interest:
Date: Tue, 27 Nov 2007 15:59:06 -0800 (GMT-08:00)
From: Dan Asimov <[EMAIL PROTECTED]>
To: math-fun <[EMAIL PROTECTED]>
Euler number (often called "Euler characteristic") for nicely
behaved topological spaces is standard terminology.
One large class of "nicely behaved" spaces is those that can be
triangulated, and this include all those that can be expressed as a
union of simple closed polygons (including interiors) meeting only
along common edges and/or common vertices.
The definition of Euler characteristic X(S) for such a planar set S is
X(S) = V-E+F
(where the X is written as a script xi) and is a topological
invariant. (So it doesn't depend on how the space is decomposed
into a nice union of
The area of a Go board occupied by certain pieces may be thought of
as the union of squares, one per piece, meeting (when they do) along
common edges.
(Such squares would be thought of as centered at any of the 361
dots, with side length equal to the distance between adjacent dots.)
So to calculate the Euler characteristic of a set of pieces on a Go
board, just consider each piece to be a square with 4 Vertices, 4
Edges, and 1 Face. Each Vertices and Edges must be counted only
once, even if it belongs to more than one square.)
To implement this, maintain one array for all (19+1)^2 = 400
Vertices, one for all 2*19*(19+1) = 760 Edges, and one for all 19^2
= 361 Faces, zeroing these all out at the start. Whenever a piece
in the set S of interest is encountered, ensure that all 9 = 4+4+1
relevant array values are set to 1, not 0. Finally, calculate X(S) = V-E+F.
There is a simple relationship between X(S) and the number H of holes in S:
H = 1 - X.
(As a check, note that a full board has H = 1-(400-760+361) = 0 holes.)
Hope this helps.
--Dan
_______________________________________________
math-fun mailing list
[EMAIL PROTECTED]
http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
---
vice-chair http://ocjug.org/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
