Index Ackermann’s function, 81 inverse, see inverse Ackermann function Adamec, Radek, 81 adversary (to online algorithm), 182 aﬃne copy (of point set), 143–144 Agarwal, Pankaj K., 15, 26, 27, 37–39, 48, 51, 58–63, 68, 74, 80, 81, 85, 88, 111, 112, 115, 117, 126, 142, 163, 166, 168 Ajtai, Mikl´ os, 35, 106, 124 Ajwani, Deepak, 180 Alevizos Panagiotis, 90 allowable sequence, 4 Alon, Noga, 111, 125, 188 Alt, Helmut, 36 Amato, Nancy M., 96 angle determined by point set, 144 angular resolution (of graph), 126–127 animal (set of grid cubes), 196 annulus, smallest width of, 67 antipodality, 35 Apfelbaum, Roel, 142, 145 APX-hardness, 186, 187 Arkin, Esther M., 91 Aronov, Boris, 27, 28, 31, 32, 37–39, 41, 46–48, 59, 60, 63, 111, 112, 114, 126, 161, 166, 168 arrangement, 13–71, 73, 99, 145, 150, 165 and Davenport–Schinzel sequences, 89–98 applications, 13, 49, 56, 63–70 combinatorial complexity of, 16, 89 complexity of cell in, 14, 27–29, 90–92, 99 complexity of many cells in, 37–39, 97, 99, 101, 103, 108, 109 computing, 56–58, 89 computing substructures in, 58–63 decomposition of, 49–54, 156, 157 definition, 13, 16, 89 history, 15 in complex space, 15 joint in, see lines in space, joint lattice, see lattice arrangement level in, see level of algebraic surface patches, 15, 19, 28, 55, 56, 61, 168 of arcs, 37, 58, 61, 63, 74, 90, 92, 96, 97 of circles, 15, 18, 38, 39, 63, 66, 97, 101 of graphs of polynomials, 55 of hyperplanes, 14, 15, 18, 31, 37, 39, 54, 56, 57, 60–64, 96, 98 of lines, 8, 15, 18, 34, 37, 56, 62, 74, 90, 96–98, 104, 108, 147, 170 of parabolas, 37 of planes, 18, 37, 62 of polytope boundaries, 19 of pseudo-circles, 101, 111 of pseudo-parabolas, 37 of pseudo-planes, 37 of pseudo-segments, 101 of pseudolines, 2, 36, 37 of quadrics, 148 of rays, 90 of segments, 37, 38, 55, 57, 63, 74, 90, 91, 96, 97, 110 of semi-pfaﬃan sets, 15 of simplices, 28, 31, 56 of spheres, 14, 18, 53 of triangles, 28, 37, 53, 61, 62 representation of, 54–56 zone in, see zone art gallery problem, 166 aspect graph, 165–166 orthographic, 165 perspective, 165 assembly, 69, 147 Atallah, Mikhail J., 73 Avis, David, 57, 61 Avital, Shmuel, 125 Badent, Melanie, 128 Balaban, Ivan J., 57 Balogh, J´ ozsef, 36 Bar-Noy, Amotz, 182 B´ ar´ any, Imre, 36, 37 Bar´ at, J´ anos, 127 Basu, Saugata, 19, 28, 29, 32, 69 Bereg, Sergey, 189 227

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2009 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.