Subdivision Drawings of Hypergraphs ⋆ (2009)
Michael Kaufmann, Marc Van Kreveld, Bettina Speckmann
Abstract. We introduce the concept of subdivision drawings of hypergraphs. In a subdivision drawing each vertex corresponds uniquely to a face of a planar subdivision and, for each hyperedge, the...
www.cs.uu.nl Area-Preserving Approximations of Polygonal Paths ∗† (2009)
Sergio Cabello, Otfried Cheong, Joachim Gudmundsson, Marc Van Kreveld, Bettina Speckmann, Prosenjit Bose, ...
Let P be an x-monotone polygonal path in the plane. For a path Q that approximates P let WA(Q) be the area above P and below Q, and let WB(Q) be the area above Q and below P. Given P and an integer...
Article Automated Construction of Rectangular (2009)
Marc Van Kreveld, Bettina Speckmann
A rectangular cartogram is a type of map where every region is a rectangle. The size of the rectangles is chosen such that their areas represent a geographic variable (e.g., population). Good...
Sergio Cabello, Marc Van Kreveld
This paper addresses research issues and describes a prototype implementation for the computation of schematic maps. The generated layout mainly depends on two parameters, namely the shape of the...
Matched Drawings of Planar Graphs ⋆ (2008)
Emilio Di Giacomo, Walter Didimo, Marc Van Kreveld, Bettina Speckmann
Abstract. A natural way to draw two planar graphs whose vertex sets are matched is to assign each matched pair a unique y-coordinate. In this paper we introduce the concept of such matched drawings,...
Facility Location on Terrains ⋆ (Extended Abstract) (2008)
Boris Aronov, Marc Van Kreveld, Kasturirangan Varadarajan
Abstract. Given a terrain defined as a piecewise-linear function with n triangles, and m point sites on it, we would like to identify the location on the terrain that minimizes the maximum distance...
Department of Information and Computing Sciences, Utrecht University, (2008)
Bettina Speckmann, Marc Van Kreveld, Er Florisson
Abstract. In [26], the first two authors of this paper presented the first algorithms to construct rectangular cartograms. The first step is to determine a representation of all regions by rectangles...
Prof Eva Tardos, Vlady Ravelomanana, Herve Daudé, Ivan Rapaport, Karol Suchan, Ioan Todinca, ...
15:00-15:20 Computing the growth of the number of overlap-free words with spectra
Optimization for First Order Delaunay (2008)
Marc Van Kreveld, Maarten Löffler, Rodrigo I. Silveira
Abstract. This paper discusses optimization of quality measures over first order Delaunay triangulations. Unlike most previous work, our measures relate to edge-adjacent or vertex-adjacent triangles...
1 Delineating Boundaries for Imprecise Regions ∗ (2008)
Iris Reinbacher, Marc Benkert, Marc Kreveld, Jack Snoeyink, Alexander Wolff, ...
In geographic information retrieval, queries often name geographic regions that do not have a well-defined boundary, such as “Southern France. ” We provide two algorithmic approaches to the...
Af John Ahn, Placement Cartographica, Marc Van Kreveld, Subhash Suri Label, ...
text placement within dense feature networks. In Proc. Auto-
www.cs.uu.nl Area-Preserving Approximations of Polygonal Paths ∗† (2008)
Sergio Cabello, Otfried Cheong, Joachim Gudmundsson, Marc Van Kreveld, Bettina Speckmann, Prosenjit Bose, ...
Let P be an x-monotone polygonal path in the plane. For a path Q that approximates P let WA(Q) be the area above P and below Q, and let WB(Q) be the area above Q and below P. Given P and an integer...
www.cs.uu.nl Delineating Boundaries for Imprecise Regions ∗ (2008)
Iris Reinbacher, Marc Benkert, Marc Van Kreveld, Jack Snoeyink, Alexander Wolff, ...
In geographic information retrieval, queries often utilize names of geographic regions that do not have a well-defined boundary, such as “Southern France. ” We provide two classes of algorithms...
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...
Approximating Largest Convex Hulls for Imprecise Points ∗ (2008)
Maarten Löffler, Marc Van Kreveld, Marc Kreveld, Maarten Löffler
Assume that a set of imprecise points is given, where each point is specified by a region in which the point will lie. Such a region can be modelled as a circle, square, line segment, etc. We study...
Abstract Web-based Delineation of Imprecise Regions (2008)
Avi Arampatzis, Marc Van Kreveld, Iris Reinbacher, Christopher B. Jones, Subodh Vaid, Paul Clough, ...
This paper describes several steps in the derivation of boundaries of imprecise regions using the Web as the information source. We discuss how to use the Web to obtain locations that are part of and...
On the Number of Empty Pseudo-Triangles in Point Sets (2008)
Marc Van Kreveld, Bettina Speckmann, Marc Kreveld, Bettina Speckmann
We analyze the minimum and maximum number of empty pseudo-triangles defined by any planar point set. We consider the cases where the three convex vertices are fixed and where they are not fixed....
Wooden Geometric Puzzles: Design and Hardness Proofs (2008)
Hans L. Bodlaender, Marc Van Kreveld, Günter Rote, Gerard Tel, Helmut Alt, Hans L. Bodlaender, ...
We discuss some new geometric puzzles and the complexity of their extension to arbitrary sizes. For gate puzzles and two-layer puzzles we prove NP-completeness of solving them. Not only the solution...
Magdalene G. Borgelt, Marc Van Kreveld, Magdalene G. Borgelt, Jun Luo, Marc Van Kreveld
Let P be a simple polygon of n vertices and let S be a set of N points lying in the interior of P. A geodesic disk GD(p, r) with center p and radius r is the set of points in P that have a geodesic...
www.cs.uu.nl Efficient Detection of Motion Patterns in Spatio-Temporal Data Sets ∗ (2008)
Joachim Gudmundsson, Marc Van Kreveld, Bettina Speckmann, Joachim Gudmundsson, Marc Kreveld, Bettina Speckmann
Moving point object data can be analyzed through the discovery of patterns. We consider the computational efficiency of detecting four such spatio-temporal patterns, namely flock, leadership,...
www.cs.uu.nl Approximate Unions of Lines and Minkowski Sums (2008)
Marc Van Kreveld, Marc Van Kreveld
We study the complexity of and algorithms to construct approximations of the union of lines and of the Minkowski sum of two simple polygons. We also study thick unions of lines and Minkowski sums,...
Planar Bichromatic Minimum Spanning Trees ∗ (2008)
Magdalene G. Borgelt, Marc Van Kreveld, Maarten Löffler, Damian Merrick, Rodrigo I. Silveira, Mostafa Vahedi, ...
Given a set S of n red and blue points in the plane, a planar bichromatic minimum spanning tree is the shortest possible spanning tree of S, such that every edge connects a red and a blue point, and...
www.cs.uu.nl Generating Realistic Terrains with Higher-Order (2008)
Thierry De Kok, Marc Van Kreveld, Maarten Löffler, Delaunay Triangulations, Thierry Kok, ...
For hydrologic applications, terrain models should have few local minima, and drainage lines should coincide with edges. We show that triangulating a set of points with elevations such that the...
Tycho Strijk, Marc Van Kreveld
Given a rectilinear map consisting of n disjoint line segments, the corresponding labeling problem is to place a rectangle at each segment, allowing three possible positions, such that the rectangles...
A New Approach to Subdivision Simpli cation (2008)
Mark De Berg, Marc Van Kreveld, Stefan Schirra
The line simpli cation problem is an old and well-studied problem in cartography. Although there are several algorithms to compute a simpli cation, there seem to be no algorithms that perform line...
Scale Dependent Definitions of Gradient and Aspect (2008)
Iris Reinbacher, Marc Van Kreveld, Tim Adelaar, Marc Benkert, Iris Reinbacher, Marc Kreveld, ...
and their Computation ∗
www.cs.uu.nl On Rectangular Cartograms (2008)
Marc Van Kreveld, Bettina Speckmann, Marc Kreveld, Bettina Speckmann
A rectangular cartogram is a type of map where every region is a rectangle. The size of the rectangles is chosen such that their areas represent a geographic variable (e.g., population). Good...
Approximate Unions of Lines and Minkowski Sums (2008)
Marc Kreveld, Marc Van Kreveld
1 Introduction Minkowski sums are a basic concept in motion planning and therefore, they have been studiedextensively in computational geometry. For two sets P and Q in the plane, it is defined as P...
Higher order Delaunay triangulations (2008)
Marc Van Kreveld, Joachim Gudmundsson, Joachim Gudmundsson, Herman J. Haverkort, Herman J. Haverkort, Marc Kreveld
We extend the notion of higher-order Delaunay triangulations to constrained higherorder Delaunay triangulations and provide various results. We can determine the order k of a given triangulation in...
Finding the Wood by the Trees (2008)
We'll give a strategy to locate all trees (points) from a starting tree using a rope, navigation equipment, computation, and some memory. 1
Marc Van Kreveld, Étienne Schramm Alex, Er Wolff
This paper discusses a variety of ways to place diagrams like pie charts on maps, in particular, administrative subdivisions. The different ways come from different models of the placement problem: a...
Largest and Smallest Convex Hulls for Imprecise Points (2008)
Löffler, M., Kreveld, Marc Van
Assume that a set of imprecise points is given, where each point is specified by a region in which the point may lie. We study the problem of computing the smallest and largest possible convex hulls,...
David Bremner, Marc Van Kreveld
A polyhedron P is castable if its boundary can be partitioned by a plane into two polyhedral terrains. Such polyhedra can be manufactured easily using two cast parts. Assuming that the cast parts are...
David Bremner, Marc Van Kreveld
A polyhedron P is castable if its boundary can be partitioned by a plane into two polyhedral terrains. Castable polyhedra can be manufactured easily using two cast parts, where each cast part can be...
Marc Van Kreveld, Godfried Toussaint
In the manufacturing industry, finding an orientation for a mold that eliminates surface defects and ensures a complete fill after termination of the gravity casting process, is an important and...
Marc Van Kreveld, Godfried Toussaint
In the manufacturing industry, finding an orientation for a mold that eliminates surface defects and ensures a complete fill after termination of the gravity casting process, is an important and...
Pankaj Agarwal, Mark De Berg, Katrin Dobrint, Marc Van Kreveld, Mark Overmars, Marko De Groot, ...
Triangulated surfaces are often used to represent terrains in Geographic Information Systems (GIS); one of the primary computations on terrains is determining drainage networks. Under natural...
Pankaj Agarwal, Mark De Berg, Katrin Dobrint, Marc Van Kreveld, Mark Overmars, Marko De Groot, ...
Triangulated surfaces are often used to represent terrains in Geographic Information Systems (GIS); one of the primary computations on terrains is determining drainage networks. Under natural...
Max-Planck-Institut fur Informatik (2007)
Mark De Berg, Marc Van Kreveld, Stefan Schirra
The line simplification problem is an old and well-studied problem in cartography. Although there are several algorithms to compute a simplification, there seem to be no algorithms that perform line...
On Fat Partioning, Fat Covering and the Union Size of Polygons (2007)
M. Van Kreveld, M. Van Kreveld, Marc Van Kreveld
The complexity of the contour of the union of simple polygons with n vertices in total can be O(n 2) in general. A notion of fatness for simple polygons is introduced, which extends most of the...
Rectilinear Decompositions Low, Mark De Berg, Mark De Berg, Marc Van Kreveld, Marc Van Kreveld
Number Mark de Berg*
Marc Van Kreveld, Jack Snoeyink, Sue Whitesides
An l-ruler is a chain of n links, each of length l. The links, which are allowed to cross, are modelled by line segments whose endpoints act as joints. A given configuration of an l-ruler is said to...
David Bremner, Marc Van Kreveld
A polyhedron P is castable if its boundary can be partitioned by a plane into two polyhedral terrains. Castable polyhedra can be manufactured easily using two cast parts, where each cast part can be...
Marc Van Kreveld, Chandrajit Bajaj, Valerio Pascucci, Dan Schikore
For 2D or 3D meshes that represent a continuous function to the reals, the contours---or isosurfaces---of a specified value are an important way to visualize it. To find such contours, a seed set can...
Mark De Berg, Olivier Devillers, Marc Van Kreveld, Otfried Schwarzkopf, Monique Teillaud
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 placements of Q with respect to P...
Higher order Delaunay triangulations (2007)
Joachim Gudmundsson, Joachim Gudmundsson, Herman J. Haverkort, Herman J. Haverkort, Marc Van Kreveld, Marc Van Kreveld
We extend the notion of higher-order Delaunay triangulations to constrained higherorder Delaunay triangulations and provide various results. We can determine the order k of a given triangulation in...
Mark De Berg, Mark De Berg, Olivier Devillers, Olivier Devillers, Marc Van Kreveld, Marc Van Kreveld, ...
apport de recherche
www.cs.uu.nl On the Education of GIS Algorithm Design ∗ (2007)
Marc Van Kreveld, Marc Van Kreveld
To teach the design of algorithms in an algorithmic GIS course, it is suggested to complement lectures with a particular type of project. How such a project can be set up is discussed, as well as a...
Largest bounding box, smallest diameter, and related problems on imprecise points (2007)
Marc Van Kreveld, Maarten Löffler, Maarten Löffler, Marc Kreveld
We model imprecise points as regions in which one point must be located. We study computing the largest and smallest possible values of various basic geometric measures on sets of imprecise points,...
Optimal higher order Delaunay triangulations of polygons (2007)
Marc Van Kreveld, Rodrigo I. Silveira, Rodrigo I. Silveira, Marc Kreveld
This paper presents an algorithm to triangulate polygons optimally using order-k Delaunay triangulations, for a number of quality measures. The algorithm uses properties of higher order Delaunay...
Optimization for first order delaunay triangulations (2007)
Marc Van Kreveld, Marc Kreveld, Maarten Löffler, Maarten Löffler, Rodrigo I. Silveira, Rodrigo I. Silveira
This paper discusses optimization of quality measures over first order Delaunay triangulations. Unlike most previous work, our measures relate to edge-adjacent or vertex-adjacent triangles instead of...
Towards a definition of higher order constrained Delaunay triangulations (2007)
Rodrigo I. Silveira, Marc Van Kreveld
When a triangulation of a set of points and edges is required, the constrained Delaunay triangulation is often the preferred choice because of its well-shaped triangles. However, in applications like...
Region-restricted clustering for geographic data mining (2006)
Joachim Gudmundsson, Joachim Gudmundsson, Marc Van Kreveld, Marc Van Kreveld, Giri Narasimhan, Giri Narasimhan
mining
Largest and smallest convex hulls for imprecise points (2006)
Marc Van Kreveld, Maarten Löffler, Maarten Löffler, Marc Kreveld
Assume that a set of imprecise points is given, where each point is specified by a region in which the point may lie. We study the problem of computing the smallest and largest possible convex hulls,...
Esther Moet, Marc Van Kreveld, Esther Moet, Marc Van Kreveld
We study worst-case complexities of visibility and distance structures on terrains under realistic assumptions on edge length ratios and the angles of the triangles, and a more general low-density...
Schematisation of Tree Drawings (2006)
Joachim Gudmundsson, Marc Van Kreveld, Damian Merrick
Abstract. Given a tree T spanning a set of points S in the plane, we study the problem of drawing T using only line segments aligned with a fixed set of directions C. The vertices in the drawing must...
Algorithmic aspects of proportional symbol maps (2006)
Sergio Cabello, Herman Haverkort, Marc Van Kreveld, Bettina Speckmann, Sergio Cabello
Proportional symbol maps visualize numerical data associated with point locations by placing a scaled symbol—typically an opaque disk or square—at the corresponding point on a map. The area of...
Schematisation of Tree Drawings (2006)
Joachim Gudmundsson, Marc Van Kreveld, Damian Merrick
Abstract. Given a tree T spanning a set of points S in the plane, we study the problem of drawing T using only line segments aligned with a fixed set of directions C. The vertices in the drawing must...
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...
Delineating boundaries of imprecise regions (2005)
Iris Reinbacher, Marc Benkert, Marc Van Kreveld, Er Wolff
Abstract. In geographic information retrieval, queries often use names of geographic regions that do not have a well-defined boundary, such as “Southern France. ” We provide two classes of...
Prosenjit Bose, Marc Van Kreveld, Marc Van Kreveld
A simple polyhedron is weakly-monotonic in direction � d provided that the intersection of the polyhedron and any plane with normal � d is simply-connected (i.e. empty, a point, a line-segment or...
Visibility Maps of Segments and Triangles in 3D* (2005)
Esther Moet, Christian Knauer, Marc Van Kreveld
1 Introduction Computations concerning visibility and the generation of shadows are important to obtain realisticimages in computer graphics. Unfortunately, these computations can be very...
www.cs.uu.nl Visibility Maps of Segments and Triangles in 3D ∗ (2005)
Esther Moet, Christian Knauer, Marc Van Kreveld, Esther Moet, Christian Knauer, Marc Van Kreveld
Let T be a set of n triangles in three-dimensional space, let s be a line segment, and let t be a triangle, both disjoint from T. We consider the visibility map of s with respect to T, i.e., the...
www.cs.uu.nl Region Intervisibility in Terrains (2005)
Esther Moet, Marc Van Kreveld, René Van Oostrum, Esther Moet, Marc Kreveld, René Oostrum
A polyhedral terrain is the graph of a continuous piecewise linear function defined over the triangles of a triangulation in the xy-plane. Two points on or above a terrain are visible to each other...
Web-Based Delineation of Imprecise Regions (2004)
Avi Arampatzis Marc, Marc Van Kreveld, Iris Reinbacher, Christopher B. Jones, Subodh Vaid
This paper describes several steps in the derivation of boundaries of imprecise regions using the Web as the information source (see also [4]). We discuss how to obtain locations that are part and...
Distributed Ranking Methods for Geographic Information Retrieval (2004)
Marc Van Kreveld, Marc Kreveld, Iris Reinbacher, Iris Reinbacher, Avi Arampatzis, Avi Arampatzis, ...
Geographic Information Retrieval is concerned with retrieving documents in response to a spatially related query. This paper addresses the ranking of documents by both textual and spatial relevance....
Web-based delineation of imprecise regions (2004)
Avi Arampatzis, Marc Van Kreveld, Iris Reinbacher, Christopher B. Jones, Subodh Vaid, Paul Clough, ...
This paper describes several steps in the derivation of boundaries of imprecise regions using the Web as the information source. We discuss how to use the Web to obtain locations that are part of and...
Web-based delineation of imprecise regions (2004)
Avi Arampatzis, Marc Van Kreveld, Iris Reinbacher, Christopher B. Jones, Subodh Vaid
Geographical information tools such as online maps and gazetteers have been increasingly developed and become available on the World Wide Web. Such resources are of interest not only in geographic...
Web-based delineation of imprecise regions (2004)
Avi Arampatzis, Marc Van Kreveld, Iris Reinbacher, Christopher B. Jones, Subodh Vaid
Geographical information tools such as online maps and gazetteers have been increasingly developed and become available on the World Wide Web. Such resources are of interest not only in geographic...
Abstract Multi-Attribute Similarity Ranking Deliverable number: D17:5301 (2004)
Spirit Eu, Ist Programme, Deliverable Type R, Avi Arampatzis, Marc Van Kreveld, Iris Reinbacher
In the previous two deliverables we introduced, firstly, simple geometric formulas to calculate spatial scores between footprints, and secondly, ways to combine spatial with textual scores in order...
Approximation algorithms for aligning points (2003)
Marc Van Kreveld, Sergio Cabello, Sergio Cabello, Marc Kreveld
We study the problem of aligning as many points as possible horizontally, vertically, or diagonally, when each point is allowed to be placed anywhere in its own, given region. Dierent shapes of...
Translating a regular grid over a point set (2003)
Marc Van Kreveld, Anil Maheshwari, Pat Morin, Jason Morrison
We consider the problem of translating a ( nite or innite) square grid G over a set S of n points in the plane in order to maximize some objective function. We say that a grid cell is k-occupied if...
Translating a regular grid over a point set (2003)
Marc Van Kreveld, Anil Maheshwari, Pat Morin, Jason Morrison
We consider the problem of translating a ( nite or innite) square grid G over a set S of n points in the plane in order to maximize some objective function. We say that a grid cell is k-occupied if...
Translating a regular grid over a point set (2003)
Marc Van Kreveld, Anil Maheshwari, Pat Morin, Jason Morrison
We consider the problem of translating a ( nite or innite) square grid G over a set S of n points in the plane in order to maximize some objective function. We say that a grid cell is k-occupied if...
Good NEWS: Partitioning a Simple Polygon by Compass Directions (2003)
Marc Van Kreveld, Marc Van Kreveld, Iris Reinbacher, Iris Reinbacher
Motivated by geographic information retrieval, we study the problem of partitioning a simple polygon into four parts that can be considered as the North, East, West, and South.
Approximation algorithms for aligning points (2003)
Marc Van Kreveld, Sergio Cabello, Sergio Cabello, Marc Kreveld
We study the problem of aligning as many points as possible horizontally, vertically, or diagonally, when each point is allowed to be placed anywhere in its own, given region. Different shapes of...
Cutting a country for smallest square fit (2002)
Marc Van Kreveld, Bettina Speckmann
Abstract. We study the problem of cutting a simple polygon with n vertices into two pieces such that – if we reposition one piece disjoint of the other, without rotation – they have the minimum...
Towards an evaluation of quality for names placement methods (2002)
Steven Van Dijk, Marc Van Kreveld, Tycho Strijk, Alexander Wol
The cartographic labeling problem is the problem of placing text on a map. This includes the positioning of the labels, and determining the shape in the case of line and area feature labels. There...
Translating a Regular Grid over a Point Set (2001)
Bose, Prosenjit, Kreveld, Marc Van, Maheshwari, A. (Anil), Morin, P. (Pat), Morrison, J. (Jason)
We consider the problem of translating a (finite or infinite) square grid G over a set S of n points in the plane in order to maximize some objective function. We say that a grid cell is k-occupied...
Schematization of road networks (2001)
Sergio Cabello, Mark De Berg, Steven Van Dijk, Marc Van Kreveld, Tycho Strijk
We study the problem of computing schematized versions of network maps, like railroad maps. Every path of the schematized map has two or three links with restricted orientations, and topologically,...
Kreveld, Labeling a rectilinear map more efficiently (1999)
Tycho Strijk, Marc Van Kreveld
Given a rectilinear map consisting of n disjoint line segments, the corresponding labeling problem is to place a rectangle at each segment, allowing three possible positions, such that the rectangles...
Point labeling with sliding labels (1999)
Marc Van Kreveld, Tycho Strijk, Alexander Wol
This paper discusses algorithms for labeling sets of points in the plane, where labels are not restricted to some nite number of positions. We show that continuously sliding labels allows more points...
Practical Extensions of Point Labeling in the Slider Model (1999)
Tycho Strijk, Marc Van Kreveld
This paper extends on research by the authors together with Alexander Wol# on point label placement using a model where labels can be placed at any position that touches the point (the slider model)....
Practical Extensions of Point Labeling in the Slider Model (1999)
Tycho Strijk Dept, Tycho Strijk, Marc Van Kreveld
This paper extends on research by the authors together with Alexander Wol# on point label placement using a model where labels can be placed at any position that touches the point (the slider model)....
Practical Extensions of Point Labeling in the Slider Model (1999)
Tycho Strijk, Marc Van Kreveld
This paper extends on research by the authors together with Alexander Wol# on point label placement using a model where labels can be placed at any position that touches the point (the slider model)....
A Simple and Efficient Algorithm for High-Quality Line Labeling (1999)
Alexander Wolff, Lars Knipping, Marc Van Kreveld, Tycho Strijk, Pankaj K. Agarwal
The interest in algorithms that automatically place labels on maps, graphs, or diagrams has increased with the advance in type-setting technology and the amount of information to be visualized....
Efficient Algorithms for Maximum Regression Depth (1999)
Marc Van Kreveld, Peter Rousseeuw, Micha Sharir, Jack Snoeyink, Bettina Speckmann
We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual...
Labeling a Rectilinear Map More Efficiently (1999)
Tycho Strijk, Marc Van Kreveld
Given a rectilinear map consisting of n disjoint line segments, the corresponding labeling problem is to place a rectangle at each segment, allowing three possible positions, such that the rectangles...
Point Labeling with Sliding Labels (1999)
Marc Van Kreveld, Tycho Strijk, Alexander Wolff
This paper discusses algorithms for labeling sets of points in the plane, where labels are not restricted to some nite number of positions. We show that continuously sliding labels allow more points...
Contour trees and small seed sets for isosurface traversal (1998)
Chandrajit Bajaj, Marc Van Kreveld, Ren'e Van Oostrum, Valerio Pascucci, Daniel R. Schikore
For 2D or 3D meshes that represent the domain of continuous function to the reals, the contours---or isosurfaces---of a specified value are an important way to visualize the function. To find such...
Facility location on terrains (1998)
Boris Aronov, Marc Van Kreveld, René Van Oostrum, Kasturi Varadarajan
Given a terrain defined as a piecewise-linear function with n triangles, and m point sites on it, we would like to identify the location on the terrain that minimizes the maximum distance to the...
Label placement by maximum independent set in rectangles (1998)
Pankaj K. Agarwal, Marc Van Kreveld, Subhash Suri
Motivated by the problem of labeling maps, we investigate the problem of computing a large non-intersecting subset in a set of n rectangles in the plane. Our results are as follows. In O(n log n)...
Point Set Labeling with Sliding Labels (1998)
Marc Van Kreveld, Tycho Strijk, Alexander Wolff
This paper discusses algorithms for labeling sets of points in the plane, where labels are not restricted to some finite number of positions. We show that continuously sliding labels allows more...
Finding the Wood by the Trees (1998)
We'll give a strategy to locate all trees (points) from a starting tree using a rope, navigation equipment, computation, and some memory. 1 Introduction It is a well-known fact that it is...
Computing the Maximum Overlap of Two Convex Polygons Under Translations. (1998)
Berg, Mark De, Devillers, Olivier, Kreveld, Marc Van, Schwarzkopf, Otfried, Teillaud, Monique
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 placements of Q with respect to P...
Computing the Maximum Overlap of Two Convex Polygons Under Translations. (1998)
Berg, Mark De, Devillers, Olivier, Kreveld, Marc Van, Schwarzkopf, Otfried, Teillaud, Monique
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 placements of Q with respect to P...
Algorithms on triangulated terrains (1997)
Abstract. Digital elevation models can represent many types of geographic data. One of the common digital elevation models is the triangulated irregular network (also called TIN, or polyhedral...
Simple traversal of a subdivision without extra storage (1997)
Mark De Berg, Marc Van Kreveld, Ren'e Van Oostrum, Mark Overmars
In this paper we show how to traverse a subdivision and to report all cells, edges and vertices, without making use of mark bits in the structure or a stack. We do this by performing a depth-first...
Algorithms on triangulated terrains (1997)
Digital elevation models can represent many types of geographic data. One of the common digital elevation models is the triangulated irregular network (also called TIN, or polyhedral terrain, or...
Linear-time reconstruction of Delaunay triangulations with applications (1997)
Jack Snoeyink, Marc Van Kreveld
Many of the computational geometers' favorite data structures are planar graphs, canonically determined by a set of geometric data, that take \Theta(n log n) time to compute. Examples include...
Contour Trees and Small Seed Sets for Isosurface Traversal (1997)
Marc Van Kreveld, René Van Oostrum, Chandrajit Bajaj, Valerio Pascucci, Dan Schikore
For 2D or 3D meshes that represent a continuous function to the reals, the contours -- or isosurfaces -- of a specified value are an importantway to visualize it. To find such contours, a seed set...
Linear-time reconstruction of Delaunay triangulations with applications (1997)
Jack Snoeyink, Marc Van Kreveld
Many of the computational geometers' favorite data structures are planar graphs, canonically determined by a set of geometric data, that take \Theta(n log n) time to compute. Examples include...
Simple traversal of a subdivision without extra storage (1997)
Mark De Berg, Marc Van Kreveld, Rene Van Oostrum, Mark Overmars
In this paper we show how to traverse a subdivision and to report all cells, edges and vertices, without making use of mark bits in the structure or a stack. We do this by performing a depth- rst...
Algorithms on triangulated terrains (1997)
Digital elevation models can represent many types of geographic data. One of the common digital elevation models is the triangulated irregular network (also called TIN, or polyhedral terrain, or...
Computing the Maximum Overlap of Two Convex Polygons Under Translations (1996)
Berg, Mark De, Devillers, Olivier, Kreveld, Marc Van, Schwarzkopf, Otfried, Teillaud, Monique
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 placements of $Q$ with...
Computing the Maximum Overlap of Two Convex Polygons Under Translations (1996)
Berg, Mark De, Devillers, Olivier, Kreveld, Marc Van, Schwarzkopf, Otfried, Teillaud, Monique
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 placements of $Q$ with...
Drainage queries in TINs: from local to global and back again (1996)
Sidi Yu, Marc Van Kreveld, Jack Snoeyink
This paper considers the cost of preprocessing a digital terrain model (DTM) represented as a triangulated irregular network (TIN) so that drainage queries---e.g., what is the watershed of a query...
Two novel applications of the plane sweep paradigm are demonstrated, namely, for the computation of extended viewsheds on gridded DEMs and for class interval selection on TIN-based DEMs. In both...
Computing the Maximum Overlap of Two Convex Polygons Under Translations (1996)
Mark De Berg, Mark De Berg, Olivier Devillers, Olivier Devillers, Marc Van Kreveld, Marc Van Kreveld, ...
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 placements of Q with respect to P...
Computing the Maximum Overlap of Two Convex Polygons Under Translations (1996)
Mark De Berg, Otfried Cheong, Olivier Devillers, Marc Van Kreveld, Monique Teillaud
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 placements of Q with respect to P...
Computing the Maximum Overlap of Two Convex Polygons Under Translations (1996)
Mark De, Mark De Berg, Otfried Cheong, Olivier Devillers, Marc Van Kreveld, Monique Teillaud
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 placements of Q with respect to P...
Folding Rulers inside Triangles (1996)
Marc Van Kreveld, Jack Snoeyink, Sue Whitesides
An l-ruler is a chain of n links, each of length l. The links, which are allowed to cross, are modelled by line segments whose endpoints act as joints. A given configuration of an l-ruler is said to...
Two novel applications of the plane sweep paradigm are demonstrated, namely, for the computation of extended viewsheds on gridded DEMs and for class interval selection on TIN-based DEMs. In both...
Two- and three-dimensional point location in rectangular subdivisions (1995)
Mark De Berg, Marc Van Kreveld, Jack Snoeyink
We apply van Emde Boas-type stratified trees to point location problems in rectangular subdivisions in 2 and 3 dimensions. In a subdivision with n rectangles having integer coordinates from [0; U...
A data structure is presented to store a triangulated irregular network digital elevation model, from which isolines (contour lines) can be extracted very efficiently. If the network is based on n...
Determining the Castability of Simple Polyhedra (1994)
Prosenjit Bose, David Bremner, Marc Van Kreveld
A polyhedron P is castable if its boundary can be partitioned by a plane into two polyhedral terrains. Castable polyhedra can be manufactured easily using two cast parts, where each cast part can be...
Connected component and simple polygon intersection searching (1993)
Pankaj K. Agarwal, Marc Van Kreveld
Efficient data structures are given for the following two query problems: preprocess a set P of simple polygons with a total of n edges, so that all polygons of P intersected by a query segment can...
Filling Polyhedral Molds (1993)
Prosenjit Bose, Marc Van Kreveld, Godfried Toussaint, Ha A
In the manufacturing industry, finding an orientation for a mold that eliminates surface defects and insures a complete fill after termination of the gravity casting process, is an important and...
Connected Component and Simple Polygon Intersection Searching (1993)
Marc Kreveld, Pankaj Agarwal, Pankaj K. Agarwal, Marc Van Kreveld
Efficient data structures are given for the following two query problems: preprocess a set P of simple polygons with a total of n edges, so that all polygons of P intersected by a query segment can...
Intersection queries in sets of disks (1992)
Marc Van Kreveld, Marc Van Kreveld, Mark Overmars, Mark Overmars, Pankaj Agarwal, Pankaj Agarwal, ...
data structures exist that store axis-parallel objects like horizontal line segments or rectangles. Only recently structures have been designed that store sets of arbitrarily oriented line segments...
Marc Van Kreveld, Pankaj K. Agarwal, Pankaj K. Agarwal, Marc Van Kreveld
Let S be a set of n (possibly intersecting) line segments in the plane. We show that the arrangement of S can be stored implicitly into a data structure of size O(n log 2 n) so that the following...
Sparse Arrangements and the Number of Views of Polyhedral Scenes (1991)
Mark De Berg, Dan Halperin, Mark H. Overmars, Marc Van Kreveld
In this paper we study several instances of the problem of determining the maximum number of topologically distinct two-dimensional images that three-dimensional scenes can induce. To bound this...