Abstract The two-watchman route problem is that of computing a pair of closed tours in an environment so that the two tours together see the whole environment and some length measure on the two tours is minimized. Two standard measures are: the minmax measure, where we want the tours where the longest of them has smallest length, and the minsum measure, where we want the tours for which the sum of their lengths is the smallest. It is known that computing a minmax two-watchman route is NP-hard for simple rectilinear polygons and thus also for simple polygons. Also, any c-approximation algorithm for the minmax two-watchman route is automatically a 2c-approximation algorithm for the minsum two-watchman route. We exhibit two constant factor approximation algorithms for computing minmax two-watchman routes in simple polygons with approximation factors 5.969 and 11.939, having running times $$O(n^8)$$ O ( n 8 ) and $$O(n^4)$$ O ( n 4 ) respectively, where n is the number of vertices of the polygon. We also use the same techniques to obtain a 6.922-approximation for the fixed two-watchman route problem running in $$O(n^2)$$ O ( n 2 ) time, i.e., when two starting points of the two tours are given as input.

We propose a novel approach of distance-based spatial clustering and contribute a heuristic computation of input parameters for guiding users in the search of interesting cluster constellations. We thereby combine computational geometry with interactive visualization into one coherent framework. Our approach entails displaying the results of the heuristics to users, as shown in Figure 1, providing a setting from which to start the exploration and data analysis. Addition interaction capabilities are available containing visual feedback for exploring further clustering options and is able to cope with noise in the data. We evaluate, and show the benefits of our approach on a sophisticated artificial dataset and demonstrate its usefulness on real-world data.

Analyzing the occurrence of stops in transportation systems is an important challenge to better understand traffic congestion problems and find corresponding solutions. We propose an efficient system to analyze stop occurrences. It consists of two major parts: (1) an efficient clustering algorithm to partition the stops into groups based on strongly connected components (2) an interactive visual representation of the results to provide insights to domain experts.

Various software applications deal with analyzing the textual content of screen captures. Interpreting these images as text poses several challenges, relative to images traditionally handled by optical character recognition (OCR) engines. One such challenge is caused by text antialiasing, a technique which blurs the edges of characters, to reduce jagged appearance. This blurring changes the character images according to context, and can sometimes fuse them together. In this paper, we offer a low-cost method that can be used as a preprocessing stage, prior to OCR. Our method locates antialiased text in a screen image and segments it into separate character images. Our proposed algorithm significantly improves OCR results, particularly in images with colored text of small font size, such as in graphic user interface (GUI) screens.

We present a new classification engine based on the concept of α-shapes. Our technique is easy to implement and use, time-effective and generates good recognition results. We show how to efficiently use the concept of α-shapes of low dimension to support data in arbitrary dimension, thus overcoming the lack of α-shape algorithms in high dimensions. We further show how to inelegantly choose suitable α's to capture desirable shapes that tightly bound the data. We present experiments showing that our technique generates good results with Optical Character Recognition (OCR) tasks. Based also on strong theoretic properties, we believe that our technique can serve as a desirable classification engine for various domains in addition to OCR.

We present a novel technique for reconstructing sharp features in surface models. The algorithm is designed to fit sharp features of low algebraic and combinatorial complexity in the gaps between smooth surface patches.

We propose heuristics for visibility coverage of a polygon with the fewest point guards. This optimal coverage problem, often called the “art gallery problem”, is known to be NP-hard, so most recent research has focused on heuristics and approximation methods. We evaluate our heuristics through experimentation, comparing the upper bounds on the optimal guard number given by our methods with computed lower bounds based on heuristics for placing a large number of visibility-independent “witness points”. We give experimental evidence that our heuristics perform well in practice, on a large suite of input data; often the heuristics give a provably optimal result, while in other cases there is only a small gap between the computed upper and lower bounds on the optimal guard number.

Snap Rounding and its variant, Iterated Snap Rounding, are methods for converting arbitrary-precision arrangements of segments into a fixed-precision representation (we call them SR and ISR for short). Both methods approximate each original segment by a polygonal chain, and both may lead, for certain inputs, to rounded arrangements with undesirable properties: in SR the distance between a vertex and a non-incident edge of the rounded arrangement can be extremely small, inducing potential degeneracies. In ISR, a vertex and a non-incident edge are well separated, but the approximating chain may drift far away from the original segment it approximates. We propose a new variant, Iterated Snap Rounding with Bounded Drift, which overcomes these two shortcomings of the earlier methods. The new solution augments ISR with simple and efficient procedures that guarantee the quality of the geometric approximation of the original segments, while still maintaining the property that a vertex and a non-incident edge in the rounded arrangement are well separated. We investigate the properties of the new method and compare it with the earlier variants. We have implemented the new scheme on top of CGAL, the Computational Geometry Algorithms Library, and report on experimental results.