Approximate Range Searching Using Binary Space Partitions (2009)
We show how any BSP tree TP for the endpoints of a set of n disjoint segments in the plane can be used to obtain a BSP tree of size O(n · depth(TP)) for the segments themselves, such that the...
and Problem Complexity]: Nonnumerical Algorithms and Problems—Geometrical (2009)
Lars Arge, Mark Berg, Herman J. Haverkort, Ke Yi
We present the Priority R-tree, or PR-tree, which is the first R-tree variant that always answers a window query using O((N/B) 1−1/d + T/B) I/Os, where N is the number of ddimensional (hyper-)...
Out-of-Order Event Processing in Kinetic Data Structures* (2008)
Mohammad Ali, Abam Pankaj, K. Agarwal, Mark Berg, Hai Yu
Abstract We study the problem of designing kinetic data structures (KDS's for short) when event timescannot be computed exactly and events may be processed in a wrong order. In traditional...
Abstract I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions (2008)
Mark Berg, Herman Haverkort, Shripad Thite, Laura Toma
We present improved and simplified i/o-efficient algorithms for two problems on planar low-density subdivisions, namely map overlay and point location. More precisely, we show how to preprocess a...
I/O-Efficient Flow Modeling on Fat Terrains (2008)
Mark Berg, Otfried Cheong, Herman Haverkort, Jung-gun Lim, Laura Toma
We study the flow of water on fat terrains, that is, triangulated terrains where the minimum angle of any triangle is bounded from below by a positive constant. We show that the worstcase complexity...
River networks and watershed maps of triangulated terrains revisited ∗ (2008)
Hee-kap Ahn, Mark Berg, Otfried Cheong, Herman Haverkort, Laura Toma
Triangulated surfaces are often used to represent terrains in geographic information systems. We investigate the complexity of river networks and watershed maps on such terrains under the assumption...
Rectilinear Cartograms, Mark Berg, Elena Mumford, Bettina Speckmann
A cartogram is a thematic map that visualizes statistical data about a set of regions like countries, states or provinces. The size of a region in a cartogram corresponds to a particular geographic...
I/O-Efficient Flow Modeling on Fat Terrains (2008)
Mark Berg, Otfried Cheong, Herman Haverkort, Jung-gun Lim, Laura Toma
We study the flow of water on fat terrains, that is, triangulated terrains where the minimum angle of any triangle is bounded from below by a positive constant. We show that the worstcase complexity...
Ray Shooting Amidst Fat Convex Polyhedra in 3-Space (2008)
Boris Aronov, Mark Berg, Chris Gray
We present a data structure for ray-shooting queries in a set of convex fat polyhedra of total complexity n in R 3. The data structure uses O(n 2+ε) storage and preprocessing time, and queries can...
Rectilinear Cartograms, Mark Berg, Elena Mumford, Bettina Speckmann
A cartogram is a thematic map that visualizes statistical data about a set of regions like countries, states or provinces. The size of a region in a cartogram corresponds to a particular geographic...
Maximizing the Area of Overlap of two Unions of Disks under Rigid Motion ∗ (2008)
Mark Berg, Sergio Cabello, Panos Giannopoulos, Christian Knauer, René Oostrum, Remco C. Veltkamp
Let A and B be two sets of n resp. m disjoint unit disks in the plane, with m ≥ n. We consider the problem of finding a translation or rigid motion of A that maximizes the total area of overlap...
Out-of-Order Event Processing in Kinetic Data Structures ∗ (2008)
Mohammad Ali, Abam Pankaj, K. Agarwal, Mark Berg, Hai Yu
We study the problem of designing kinetic data structures (KDS’s for short) when event times cannot be computed exactly and events may be processed in a wrong order. In traditional KDS’s this can...
I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions ∗ (2008)
Mark Berg, Herman Haverkort, Shripad Thite, Laura Toma
We present improved and simplified i/o-efficient algorithms for two problems on planar lowdensity subdivisions, namely map overlay and point location. More precisely, we show how to preprocess a...
An intersection-sensitive algorithm for snap rounding (2008)
Mark Berg, Dan Halperin, Mark Overmars
Snap rounding is a method for converting arbitrary-precision arrangements of segments into fixed-precision representation. We present an algorithm for snap rounding with running time O((n + I)log n),...
Motion Planning in Environments with Low Obstacle Density y (2008)
A. Frank, H. Overmars, Mark Berg, Jules Vleugels
We present a simple and e cient paradigm for computing the exact solution of the motion planning problem in environments with a low obstacle density. Such environments frequently occur in practical...
www.cs.uu.nl Schematization of Networks ∗ (2008)
Sergio Cabello, Mark De Berg, Marc Van Kreveld, Sergio Cabello, Mark Berg, Marc Kreveld
We study the problem of computing schematized versions of network maps, like railroad or highway maps. Every path of the schematized map has two or three links with restricted orientations, and the...
Realistic Input Models for Geometric Algorithms (2008)
Mark Berg, Matthew J. Katz, Jules Vleugels
Many algorithms developed in computational geometry are needlessly complicated and slow because they have to be prepared for very complicated, hypothetical inputs. To avoid this, realistic models are...
Models and Motion Planning (2008)
Mark Berg, Matthew J. Katz, Mark H. Overmars, A. Frank
We study the complexity of the motion planning problem for a bounded-reach robot in the situation where the n obstacles in its workspace satisfy two of the realistic models proposed in the...
The Union of Moving Polygonal Pseudodiscs { Combinatorial Bounds and Applications (2008)
Mark Berg, Hazel Everett, Leonidas J. Guibas
Let P be a set of polygonal pseudodiscs in the plane with n edges in total translating with xed velocities in xed directions. We prove that the maximum number of combinatorial changes in the union of...
An intersection-sensitive algorithm for snap rounding (2008)
Mark Berg, Dan Halperin, Mark Overmars
Snap rounding is a method for converting arbitrary-precision arrangements of segments into fixed-precision representation. We present an algorithm for snap rounding with running time O((n + I)logn),...
Computing a Single Cell in the Overlay of two Simple Polygons? (2008)
Mark Berg, Olivier Devillers, Katrin Dobrindt, Otfried Schwarzkopf A
This note combines the lazy randomized incremental construction scheme with the technique of \connectivity acceleration " to obtain an O(n(log? n) 2) time randomized algorithm to compute a...
Guarding Scenes against Invasive Hypercubes ∗ (2008)
Mark Berg, Haggai David, Matthew J. Katz, Mark Overmars, A. Frank
In recent years realistic input models for geometric algorithms have been studied. The most important models introduced are fatness, low density, unclutteredness, and small simple-cover complexity....
www.cs.uu.nl Significant-Presence Range Queries in Categorical Data (2008)
Mark De Berg, Herman J. Haverkort, Mark Berg, Herman J. Haverkort
In traditional colored range-searching problems, one wants to store a set of n objects with m distinct colors for the following queries: report all colors such that there is at least one object of...
An intersection-sensitive algorithm for snap rounding (2008)
Mark Berg, Dan Halperin, Mark Overmars
Snap rounding is a method for converting arbitrary-precision arrangements of segments into fixed-precision representation. We present an algorithm for snap rounding with running time O((n + I)log n),...
Robust Genetic Algorithms for High Quality Map Labeling (2007)
Steven Dijk, Dirk Thierens, Mark Berg
The problem of placing labels on maps has been around for about twenty years and has proven to be a dicult one. A variety of methods has been proposed to generate good labelings, with a wide range of...
Using Genetic Algorithms for Solving Hard Problems in GIS (2007)
Steven Dijk, Dirk Thierens, Mark Berg
Genetic Algorithms (GA's) are powerful combinatorial optimizers that are able to nd close to optimal solutions for dicult problems by applying the paradigm of evolution with natural selection....
Models and Motion Planning (2007)
Mark Berg, Matthew J. Katz, Mark H. Overmars, A. Frank
We study the complexity of the motion planning problem for a bounded-reach robot in the situation where the n obstacles in its workspace satisfy two of the realistic models proposed in the...
Guarding Scenes against Invasive Hypercubes # (2007)
Mark Berg, Haggai David, Matthew J. Katz, Mark Overmars, A. Frank
In recent years realistic input models for geometric algorithms have been studied. The most important models introduced are fatness, low density, unclutteredness, and small simple-cover complexity....
On the design and analysis of competent GAs (2007)
Steven Dijk, Dirk Thierens, Mark Berg
We study two recent theoretical models---a population-sizing model and a convergence model---and examine their assumptions to gain insights about the conditions under which GAs work well. We use...
Recovering lines with fixed linear probes Extended Abstract (2007)
Mark Berg, Jit Bose, David Bremner, William Evans, Lata Narayanan
Suppose the only access we have to an arrangement of n input lines is to "probe " the arrangement with horizontal lines. A probe returns the set of probe points which are the...
Shortest Path Queries in Rectilinear Worlds (2007)
Mark Berg, Mark Berg, Marc Kreveld, Marc Kreveld, Bengt J. Nilsson, Bengt J. Nilsson, ...
In this paper, a data structure is given for two and higher dimensional shortest path queries. For a set of n ayAs-parallel rectangles in the plane, or boxes in d-spce, and a fixed target, it is...
Motion Planning in Environments with Low Obstacle Density y (2007)
A. Frank, H. Overmars, Mark Berg, Jules Vleugels
We present a simple and efficient paradigm for computing the exact solution of the motion planning problem in environments with a low obstacle density. Such environments frequently occur in practical...
Reaching a Goal with Directional Uncertainty (2007)
Mark Berg, Mark Berg, Mark Overmars, Mark Overmars, Micha Sharir, Micha Sharir, ...
Overmars 1
Vertical ray shooting and computing depth orders for fat objects (2006)
Scientific Research (NWO) under project no. 639.023.301. We present new results for three problems dealing with a set P of n constant-complexity fat objects in 3-space. (i) We describe a data...
Covering Many or Few Points with Unit Disks (2006)
Mark Berg, Sergio Cabello, Sariel Har-peled
Let P be a set of n weighted points and let X be a constant-complexity region in the plane. We study approximation algorithms for the following two continuous facility-location problems. In the first...
Covering Many or Few Points with Unit Disks ∗ (2006)
Mark Berg, Sergio Cabello, Sariel Har-peled
Let P be a set of n weighted points. We study approximation algorithms for the following two continuous facility-location problems. In the first problem we want to place m unit disks, for a given...
Schematization of networks (2005)
Mark De Berg, Marc Van Kreveld, Sergio Cabello, Sergio Cabello, Mark Berg, Marc Kreveld
We study the problem of computing schematized versions of network maps, like railroad or highway maps. Every path of the schematized map has two or three links with restricted orientations, and the...
Sparse geometric graphs with small dilation (2005)
Boris Aronov, Mark Berg, Otfried Cheong, Joachim Gudmundsson, Herman Haverkort, Michiel Smid, ...
Given a set S of n points in R D, and an integer k such that 0 � k < n, we show that a geometric graph with vertex set S, at most n − 1 + k edges, maximum degree five, and dilation O(n/(k +...
Optimal spanners for axis-aligned rectangles (2005)
Tetsuo Asano, Mark Berg, Otfried Cheong, Hazel Everett, Herman Haverkort, Naoki Katoh, ...
The dilation of a geometric graph is the maximum, over all pairs of points in the graph, of the ratio of the Euclidean length of the shortest path between them in the graph and their Euclidean...
Significant-Presence Range Queries in Categorical Data (2004)
Mark De Berg, Mark Berg, Herman J. Haverkort, Herman J. Haverkort
In traditional colored range-searching problems, one wants to store a set of n objects with m distinct colors for the following queries: report all colors such that there is at least one object of...
On simplifying dot maps (2004)
Mark Berg, Prosenjit Bose, Otfried Cheong, Pat Morin
Dot maps—drawings of point sets—are a well known cartographic method to visualize density functions over an area. We study the problem of simplifying a given dot map: given a set P of points in...
The Priority R-Tree: A Practically Efficient and Worst-Case-Optimal R-Tree (2004)
Mark De Berg, Lars Arge, Lars Arge, Mark Berg, Herman J. Haverkort, Herman J. Haverkort, ...
We present the Priority R-tree, or PR-tree, which is the first R-tree variant that always answers a window query using O((N/B)^(1-1/d) + T/B) I/Os, where N is the number of d-dimensional (hyper-)...
Pankaj K. Agarwal, Mark Berg, Jie Gao, Leonidas J. Guibas, Sariel Har-peled
Many divide-and-conquer based geometric algorithms and order-statistics problems ask for a point that lies “in the middle ” of a given point set. We study several fundamental problems of this...
Pankaj K. Agarwal, Mark Berg, Jie Gao, Leonidas J. Guibas, Sariel Har-peled
Many divide-and-conquer based geometric algorithms and order-statistics problems ask for a point that lies “in the middle ” of a given point set. We study several fundamental problems of this...
Pankaj K. Agarwal, Mark Berg, Jie Gao, Leonidas J. Guibas, Sariel Har-peled
We study the problem of “staying in the middle”: we have a set of points moving in a geometric space and wish to maintain another point (possibly one of the given points, but not necessarily)...
On simplifying dot maps (2002)
Mark Berg, Proscnjit Bose, Otfried Chcong, Pat Morin
Dot maps drawings of point setsre a well known carlographic method to visualize density fimclions over an area. We study the problem of simplifying a given dot map: given a set P of points ill tile...
On the design and analysis of competent GAs (2002)
Steven Dijk, Dirk Thierens, Mark Berg
We study two recent theoretical models—a population-sizing model and a convergence model—and examine their assumptions to gain insights about the conditions under which GAs work well. We use...
Computing the maximum overlap of two convex polygons under translations (1998)
M. De Berg, O. Devillers, M. Van Kreveld, O. Schwarzkopf, Mark Berg, Olivier Devillers, ...
Let P be a convex polygon in the plane with n vertices and let Q be a convex polygon with m vertices. We prove that the maximum number of combinatorially distinct place-ments of Q with respect to P...
Perfect binary space partitions (1997)
Mark De Berg, Mark De Berg, Marko De Groot, Marko De Groot, Mark Berg, Marko M. Groot, ...
In this paper we discuss some results on perfect binary space partitions on sets of non-intersecting line segments in two dimensions. A binary space partition is a scheme for recursively dividing a...
Computing the Angularity Tolerance (1996)
Mark Berg, Henk Meijer, Mark Overmars, Gordon Wilfong
In computational metrology one needs to compute whether an object satis es speci cations of shape within an acceptable tolerance. To this end positions on the object are measured, resulting in a...
Cuttings and applications (1995)
P. Oi Bqid, Mark De Berg, Mark De Berg, Offtied Schwarzkopf, Mark Berg, Otfried Schwarzkopf, ...
We prove a general lemma on the existence of (1/r)-cuttings of geometric objects in I = that stisfy certain properties. We use this lemma to construct (1/r)-cuttings of (azymptotically) optimal size...
On Levels of Detail in Terrains (1995)
Mark De Berg, Mark Berg, Mark Berg
In many applications it is important that one can view a scene at different levels of detail. A prime example is flight simulation: a high level of detail is needed when flying low, whereas a low...
On Levels of Detail in Terrains (1995)
Mark Berg, Mark Berg, Mark Berg
In many applications it is important that one can view a scene at di erent levels of detail. A prime example is ight simulation: a high level of detail is needed when ying low, whereas a low level of...
On lazy randomized incremental construction (1994)
Mark Berg, Mark Berg, Mark Berg, Katrin Dobrindt, Katrin Dobrindt, Katrin Dobrindt, ...
We introduce a new type of randomized incremental algorithms. Contrary to standard randomized incremental algorithms, these lazy randomized incremental algorithms are suited for computing structures...