ISE 390 -- Programming Challenges -- Week 11 Notes This Week's Goals: To review some basic principles of geometry on rectangular and hexagonal grids. Geometric algorithms Squares and equilateral triangles (six of which make up each hexagon of a hexagonal grid) are simple enough structures that they lead to trivial solutions to many standard geometric algorithm problems: convex hulls -- Squares and equilateral triangles are inherently convex. triangulation -- Either of the two diagonals in a square triangulate it. area -- Either length * width or 1/2*altitude*base perimeter -- Either 2 * (length + width) or a+b+c intersection -- The intersection of two convex figures is convex. point location -- to test if a point is in an axis oriented square is trivial: is xmax > x > xmin and ymax > y > ymin A great WWW page on game programming with many details about hexagonal grids is http://www-cs-students.stanford.edu/~amitp/gameprog.html Dual graphs A useful concept in thinking about problems on planar subdivisions is that of a dual graph, which had one vertex for each region in the subdivision, and edges between the vertices of any two regions which are neighbors of each other. The four color problem in graph theory (that any planar graph can be colored with at most four colors) is really a statement about the chromatic number about the dual graph of a planar subdivision. In fact, the dual graph of any planar subdivision must in itself be planar -- can you show why? A useful thing to observe is that the dual graphs of both rectangular and hexagonal lattices are (slightly smaller) rectangular and hexagonal lattices. Thus whatever structure you use to represent the vertex connectivities can also represent the edge connectivities. Assigned Problems: 155 -- Count how many squares cover a given point, in a nice recursive construction. Can you do it without explicitly doing the construction? 201 -- A graph theoretic problem on a partial grid. Is it easier to represent the graph as a grid instead of adjacency matrix/lists? 260 -- A problem on a hexagonal grid. Note the slick representation as a matrix with additional adjacencies. Must the winning paths be of length equal to the grid size? Variants are called the Shannon switching game and Hex. 320 -- What are the boundary cells of a grid polygon? Is a dual graph the right representation, or is there a slicker way? 356 -- Which cells are intersected by a given circle? Do you need trigonometry or will the Pythagorian theorem suffice? Is there a slicker solution? Questions for Discussion: Which grid leads to a denser circle packing? What is the densest possible way to pack spheres?