The chromatic art gallery problem asks for the minimum number of "colors" t so that a collection of point guards, each assigned one of the t colors, can see the entire polygon subject to some conditions on the colors visible to each point. In this paper, we explore this problem for orthogonal polygons using orthogonal visibility - two points p and q are mutually visible if the smallest axis-aligned rectangle containing them lies within the polygon. Our main result establishes that for a conflict-free guarding of an orthogonal n-gon, in which at least one of the colors seen by every point is unique, the number of colors is Theta(loglog n). By contrast, the best upper bound for orthogonal polygons under standard (non-orthogonal) visibility is O(log n) colors. We also show that the number of colors needed for strong guarding of simple orthogonal polygons, where all the colors visible to a point are unique, is Theta(log n). Finally, our techniques also help us establish the first non-trivial lower bound of Omega(loglog n / logloglog n) for conflict-free guarding under standard visibility. To this end we introduce and utilize a novel discrete combinatorial structure called multicolor tableau.

Principal component analysis (PCA) is commonly used to compute a bounding box of a point set in Rd. The popularity of this heuristic lies in its speed, easy implementation and in the fact that usually, PCA bounding boxes quite well approximate the minimum-volume bounding boxes.Since there are examples of discrete points sets in the plane, showing that the worst case ratio of the volume ofthe PCA bounding box and the volume of the minimum-volume bounding box tends to infinity,we consider PCA bounding boxes for continuous sets, especially for the convex hull of a point set. Here, we contributenew upper bounds on the approximation factor of PCA bounding boxesof convex sets in R2 and R3.

In proteomics 2-dimensional gel electrophoresis (2-DE) is a separation technique for proteins. The resulting protein spots can be identified by either using picking robots and subsequent mass spectrometry or by visual cross inspection of a new gel image with an already analyzed master gel. Difficulties especially arise from inherent noise and irregular geometric distortions in 2-DE images. Aiming at the automated analysis of large series of 2-DE images, or at the even more difficult interlaboratory gel comparisons, the bottleneck is to solve the two most basic algorithmic problems with high quality: Identifying protein spots and computing a matching between two images. For the development of the analysis software CAROL at Freie Universität Berlin we have reconsidered these two problems and obtained new solutions which rely on methods from computational geometry. Their novelties are: 1. Spot detection is also possible for complex regions formed by several “merged” (usually saturated) spots; 2. User-defined landmarks are not necessary for the matching. Furthermore, images for comparison are allowed to represent different parts of the entire protein pattern, which only partially “overlap”. The implementation is done in a client server architecture to allow queries via the Internet. We also discuss and point at related theoretical questions in computational geometry.

We present an on-line strategy that enables a mobile robot with vision to explore an unknown simple polygon. We prove that the resulting tour is less than 26.5 times as long as the shortest watchman tour that could be computed off-line. Our analysis is doubly founded on a novel geometric structure called angle hull. Let D be a connected region inside a simple polygon, P. We define the angle hull of D, ${\cal AH}(D)$, to be the set of all points in P that can see two points of D at a right angle. We show that the perimeter of ${\cal AH}(D)$ cannot exceed in length the perimeter of D by more than a factor of 2. This upper bound is tight.

A new algorithmic approach to comparing 2D patterns of protein spots obtained by the 2D gel electrophoresis technique is presented. Both the matching of a local pattern vs. a full 2D gel image and the global matching between full images are discussed. The local matching algorithm relies on a data structure derived from the incremental Delaunay triangulation of a point set and a 2--step hashing technique. The approach for the global matching uses local matching for landmark settings, which in previous algorithmic solutions has been done interactively by the user. *Part of a joint research project with Deutsches Herzzentrum Berlin, supported by Deutsche Forschungsgemeinschaft, grant FL 165/4--1. **Institut fur Informatik, Freie Universitat Berlin, Takustr. 9. D-14195 Berlin E-mail: [email protected] 2 1 Introduction 1.1 Point Pattern Matching The matching problem for geometric point patterns has been subject of intensive research in the last decade. Given a point pattern P and an...

The following graph-coloring result is proved: let G be a 2-connected, bipartite, and plane graph. Then one can triangulate G in such a way that the resulting graph is 3-colorable. Such a triangulation can be computed in $O(n^2 )$ time. This result implies several new upper bounds for polygon guarding problems, including the first nontrivial upper bound for the rectilinear prison yard problem. (1) $\lfloor \frac{n}{3} \rfloor $ vertex guards are sufficient to watch the interior of a rectilinear polygon with holes. (2) $\lfloor \frac{5n}{12} \rfloor + 3$ vertex guards ($\lfloor \frac{n + 4}{3} \rfloor $ point guards) are sufficient to simultaneously watch both the interior and exterior of a rectilinear polygon. Moreover, a new lower bound of $\lfloor \frac{5n}{16} \rfloor $ vertex guards for the rectilinear prison yard problem is shown and proved to be asymptotically tight for the class of orthoconvex polygons.

Art gallery problems which have been extensively studied over the last decade ask how to station a small (minimum) set of guards in a polygon such that every point of the polygon is watched by at least one guard. The graph-theoretic formulation and solution to the gallery problem for polygons in standard form is given. A complexity analysis is carried out, and open problems are discussed.>