We propose an extension of Art Galleries in Computational Geometry towards a more real world application related definition, well suited for Evolutionary Algorithms. We introduce two additional sections inside the Art Gallery. One section defines locations where guards may be placed in order to cover the Art Gallery. A second section shall be observed by these guards. We show that our definition of a Sectional Art Gallery also includes the Regular Art Gallery as a special case. Furthermore, we present an Evolutionary Algorithm which can approach Minimum Point Guard Problems in such a way, that high quality approximations can be found in Sectional Art Galleries. Our algorithm is influenced by Particle Swarm Optimizers and Particle Filters. Depending on the application, relaxations of the problem can be handled by our algorithm. This way, state of the art methods on optimally solving Minimum Point Guard Problems in Regular Art Galleries can be outperformed by multiple guards, still reaching more than 99.99% of coverage. By running our algorithm on public data sets, we show the effectiveness of our approach in both Regular and Sectional Art Galleries.

This work examines how a classifier's output of a cut-in prediction can be mapped to a (semi-) automated car's reaction to it. Several approaches of decision making are compared using real world data of a lane change predictor for an automated longitudinal guidance system, similar to an adaptive cruise control system, as an example. We show how the decision algorithms affect the time when a new lead vehicle is selected and how much more comfortable we can decelerate given different selection strategies. We propose a novel decision algorithm and conducted a case study with a prototype research car to evaluate the subjective quality of the different approaches.

A simple polygon P with two distinguished vertices, s and t, is called a street if the two boundary chains from s to t are mutually weakly visible. We present an on-line strategy that walks from s to t, in any unknown street, on a path at most $\sqrt{2}$ times longer than the shortest path. This matches the best lower bound previously known and settles an open problem in the area of competitive path planning. (The result was simultaneously and independently obtained by the first three authors and by the last two authors. Both papers, [C. Icking, R. Klein, and E. Langetepe, Proceedings of the 16th Symposium on Theoretical Aspects in Computer Science, Lecture Notes in Comput. Sci. 1563, Springer-Verlag, Berlin, 1999, pp. 110--120] and [S. Schuierer and I. Semrau, Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science, pp. 121--131], were presented at STACS'99. The present paper contains a joint full version.)

We consider the Voronoi diagram of a set of n points in three dimensions under a convex distance function induced by an arbitrary, fixed polytope. The combinatorial complexity, i.\,e.\ the number of vertices, edges, and facets, of this diagram is shown to be in θ(n^2), which constitutes a considerable improvement to the results known so far.

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.

Let #C and #D be two convex distance functions in the plane with convex unit balls C and D. Given two points, p and q, we investigate the bisector, B(p, q), of p and q, where distance from p is measured by #C and distance from q by #D . We provide the following results. B(p, q) may consist of many connected components whose precise number can be derived from the intersection of the unit balls, C and D. The bisector can contain bounded or unbounded 2-dimensional areas. Even more surprising, pieces of the bisector may appear inside the region of all points closer to p than to q.

Article Free Access Share on Searching for the kernel of a polygon—a competitive strategy Authors: Christian Icking FernUniversität Hagen, Praktische Informatik VI, Elberfelder Str. 95, 58084 Hagen, Germany FernUniversität Hagen, Praktische Informatik VI, Elberfelder Str. 95, 58084 Hagen, GermanyView Profile , Rolf Klein FernUniversität Hagen, Praktische Informatik VI, Elberfelder Str. 95, 58084 Hagen, Germany FernUniversität Hagen, Praktische Informatik VI, Elberfelder Str. 95, 58084 Hagen, GermanyView Profile Authors Info & Claims SCG '95: Proceedings of the eleventh annual symposium on Computational geometrySeptember 1995 Pages 258–266https://doi.org/10.1145/220279.220307Published:01 September 1995Publication History 32citation359DownloadsMetricsTotal Citations32Total Downloads359Last 12 Months18Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The bisector systems of convex distance functions in 3-space are investigated and it is shown that there is a substantial difference to the Euclidean metric which cannot be observed in 2-space. This disproves the general belief that Voronoi diagrams

We consider the problem of a robot which has to find a path in an unknown simple polygon from one point s to another point t, based only on what it has seen so far. A Street is a polygon for which the two boundary chains from s to t are mutually weakly visible, and the set of streets was the only class of polygons for which a competitive search algorithm was known.

Article Convex distance functions in 3-space are different Share on Authors: Christian Icking View Profile , Rolf Klein View Profile , Ngoc-Minh Lê View Profile , Lihong Ma View Profile Authors Info & Claims SCG '93: Proceedings of the ninth annual symposium on Computational geometryJuly 1993 Pages 116–123https://doi.org/10.1145/160985.161007Published:01 July 1993 12citation252DownloadsMetricsTotal Citations12Total Downloads252Last 12 Months6Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

No abstract available.