Abstract We consider the Voronoi diagram of points in the real plane when the distance between two points a and b is given by $$L_p(a-b)$$ L p ( a - b ) where $$L_p((x,y)) = (|x|^p+|y|^p)^{1/p}.$$ L p ( ( x , y ) ) = ( | x | p + | y | p ) 1 / p . We prove that the Voronoi diagram has a limit as p converges to zero from above or from below: it is the diagram that corresponds to the distance function $$L_*((x,y)) = |xy|$$ L ∗ ( ( x , y ) ) = | x y | . In this diagram, the bisector of two points in general position consists of a line and two branches of a hyperbola that split the plane into three faces per point. We propose to name $$L_*$$ L ∗ as defined above the geometric $$L_0$$ L 0 distance.

Deciding two-guard walkability of an n-sided polygon is a well-understood problem. We study the following more general question: How far can two guards reach from a given source vertex while staying mutually visible, in the (more realistic) case that the polygon is not entirely walkable? There can be Theta(n) such maximal walks, and we show how to find all of them in O(n log n) time.

Given a set of n sites in the plane, the order-k Voronoi diagram is a planar subdivision such that all points in a region share the same k nearest sites. The order-k Voronoi diagram arises for the k-nearest-neighbor problem, and there has been a lot of work for point sites in the Euclidean metric. In this paper, we study order-k Voronoi diagrams defined by an abstract bisecting curve system that satisfies several practical axioms, and thus our study covers many concrete order-k Voronoi diagrams. We propose a randomized incremental construction algorithm that runs in O(k(n-k) log^2 n +n log^3 n) steps, where O(k(n-k)) is the number of faces in the worst case. Due to those axioms, this result applies to disjoint line segments in the L_p norm, convex polygons of constant size, points in the Karlsruhe metric, and so on. In fact, this kind of run time with a polylog factor to the number of faces was only achieved for point sites in the L_1 or Euclidean metric before.

Suppose that a circular fire spreads in the plane at unit speed. A fire fighter can build a barrier at speed v > 1. How large must v be to ensure that the fire can be contained, and how should the fire fighter proceed? We provide two results. First, we analyze the natural strategy where the fighter keeps building a barrier along the frontier of the expanding fire. We prove that this approach contains the fire if v > v_c = 2.6144... holds. Second, we show that any "spiralling" strategy must have speed v > 1.618, the golden ratio, in order to succeed.

Several recent works considered cooperative cleaning in static and dynamic environments, which incorporates a swarm of simple robots cleaning an expanding region of contaminated cells in a 2-D grid. However, even the state of the art strategy requires continuously-updated global domain information. In this work-in-progress we examine a strategy operating truly local. Neither in the beginning of a cleaning process, nor later on will our robot swarm receive any global information in order to perform the cooperative cleaning task.

In this paper we are proving the following fact. Let P be an arbitrary simple polygon, and let S be an arbitrary set of 15 points inside P. Then there exists a subset T of S that is not "visually discernible", that is, T ≠ vis(v) ∩ S holds for the visibility regions vis(v) of all points v in P. In other words, the VC-dimension $d$ of visibility regions in a simple polygon cannot exceed 14. Since Valtr [v-ggwps-98] proved in 1998 that d ∈ [6,23] holds, no progress has been made on this bound. Our reduction immediately implies a smaller upper bound to the number of guards needed to cover P by ε-net theorems.

A traveller is planning a tour from some start position, s, to a goal position g in d-dimensional space. Transportation is provided by n carriers. Each carrier is a convex object that results from intersecting finitely many closed linear subspaces; it moves at constant speed along a line. Different carriers may be assigned different velocity vectors. While using carrier C, the traveller can walk at innate speed v ≥ 0 in any direction, like a passenger on board a vessel. Whenever his current position on C is simultaneously contained in some other carrier C', the traveller can change from C to C', and continue his tour by C'.

How efficiently can we search an unknown environment for a goal in an unknown position? How much would it help if the environment were known? We answer these questions for simple polygons and for undirected graphs by providing online search strategies that are as good as the best offline search algorithms, up to a constant factor. For other settings we prove that no such online algorithms exist. We introduce a natural measure which gives reasonable results and is more realistic than pure pessimistic competitive analysis.

We are studying the problem of determining suitable meeting times and locations for a group of participants wishing to schedule a new meeting subject to already scheduled meetings possibly held at a number of different locations. Each participant must be able to reach the new meeting location, attend for the entire duration, and reach the next meeting location on time. In particular, we give a solution to the problem instance where each participant has two scheduled meetings separated by a free time interval. For a geometric model, where n participants can travel along straight paths in the Euclidean plane, we present an O(n log n) algorithm to determine the longest meeting duration and a location suitable to all participants. In a graph-based model, transportation is provided by a geometric network over m nodes and e edges in the plane. Participants can have individual weights. Moreover, there can be k groups of participants, such that only one member of each group must attend the meeting. In this model, a location for a meeting of longest possible duration can be determined in time O(enalpha(k) log k + n log n + mn log m), where alpha(k) denotes the extremely slowly growing inverse Ackermann function

Consider a plane graph G, drawn with straight lines. For every pair a,b of vertices of G, we compare the shortest-path distance between a and b in G (with Euclidean edge lengths) to their actual distance in the plane. The worst-case ratio of these two values, for all pairs of points, is called the dilation of G. All finite plane graphs of dilation 1 have been classified. They are closely related to the following iterative procedure. For a given point set P ⊆ R2, we connect every pair of points in P by a line segment and then add to P all those points where two such line segments cross. Repeating this process infinitely often, yields a limit point set P∞⊇P. This limit set P∞ is finite if and only if P is contained in the vertex set of a triangulation of dilation 1.The main result of this paper is the following gap theorem: For any finite point set P in the plane for which P∞ is infinite, there exists a threshold λ > 1 such that P is not contained in the vertex set of any finite plane graph of dilation at most λ. As a first ingredient to our proof, we show that such an infinite P∞ must lie dense in a certain region of the plane. In the second, more difficult part, we then construct a concrete point set P0 such that any planar graph that contains this set amongst its vertices must have a dilation larger than 1.0000047.

We demonstrate how one of the classical areas of computationalgeometry has reached practical application, which in turngives rise to new, fascinating geometric problems.In particular, we discuss the problem of developing a goodonline strategy for anautonomous mobile robot to locate an object that is hidden behinda corner or door.

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 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.

Traditional searching and browsing functions for bibliographic databases no longer enable researchers to deal efficiently with the rapidly growing number of scientific publications. Our project BibRelEx aggregates expert knowledge on a body of scientific literature and makes it available to researchers who wish to explore the literature. We take a two-pronged approach. First, we collect expert annotations on publications and their semantic relationships to other publications. Second, we let researchers explore this semantically enriched body of literature and knowledge through visualizations. Hence, we enable researchers to track relevant documents based on their colleagues' expertise. We are testing our approach with a bibliographic database in a computational geometry.

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 Voronoi diagrams and containment of families of convex sets on the plane Authors: M. Abellanas Universidad Politécnica de Madrid, Spain Universidad Politécnica de Madrid, SpainView Profile , G. Hernandez Universidad Politécnica de Madrid, Spain Universidad Politécnica de Madrid, SpainView Profile , R. Klein Fern Universität Hagen, Germany Fern Universität Hagen, GermanyView Profile , V. Neumann-Lara Universidad Nacional Autonoma de México, Mexico Universidad Nacional Autonoma de México, MexicoView Profile , J. Urrutia University of Ottawa, Canada University of Ottawa, CanadaView Profile Authors Info & Claims SCG '95: Proceedings of the eleventh annual symposium on Computational geometrySeptember 1995 Pages 71–78https://doi.org/10.1145/220279.220287Published:01 September 1995Publication History 3citation259DownloadsMetricsTotal Citations3Total Downloads259Last 12 Months12Last 6 weeks4 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

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

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

For a polygon P, the bounded Voronoi diagram of P is a partition of P into regions assigned to the vertices of P: A point p inside P belongs to the region of a vertex v if and only if v is the closest vertex of P visible from p. We present a randomized algorithm that builds the bounded Voronoi diagram of a simple polygon in linear expected time. Among other applications, we can construct within the same time bound the generalized Delaunay triangulation of P and the minimal spanning tree on P 's vertices that is contained in P.

Let P be a simple planar polygon. We present a linear worst-case time algorithm for constructing the bounded Voronoi diagram of P in the Manhattan metric, where each point z in P belongs to the region of the closest vertex of P that is visible from z. Among other consequences, the minimal spanning tree of the vertices in the Manhattan metric that is contained in P can be computed within optimal linear time.

No abstract available.

A polygon with two distinguished vertices, s and g, is called a street if the two boundary chains from s to g are mutually weakly visible. For a mobile robot with onboard vision, a strategy for finding a short path from s to g in a street not known in advance is described, and it is proved that the length of the path created does not exceed 1+3 pi /2 times the length of the shortest path from s to g. Experiments suggest that the strategy is much better than this, as no ratio bigger than 1.8 has yet been observed. This is complemented by a lower bound of 1.41 for the relative detour each strategy can be forced to generate.>

It is shown that the external path length of a binary tree is closely related to the ratios of means of certain integers and establish the upper bound External Path Length ≤ N(log 2 N + Δ - log 2 Δ - 0.6623), where N denotes the number of external nodes in the tree and Δ is the difference in length between a longest and shortest path. Then it is proved that this bound is tight up to an o(N) term if Δ ≤ √N. If Δ > √N , we contstruct binary trees whose external path length is at least as large as N(log 2 N + Φ(N, Δ)Δ - log 2 Δ -4) , where Φ(N, Δ) = 1/(1 + 2(Δ/N)) .

Given a point set in plane and a fixed planar region (window) a window query consists of enumerating the points in a translate of the region. A recently presented result shows that a static data structure of optimal size enables window queries for convex regions in optimal time. We show that if the windows are (maybe non-convex) polygons another data structure of optimal size supports not only window queries in optimal time but also allows updating of the point set in optimal time.