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?