Flipturning Polygons (Extended abstract) (2009)
Oswin Aichholzer, Carmen Cortés, Erik D. Demaine, Vida Dujmović, Jeff Erickson, Mark Overmars, ...
Figure 1. A flipturn. The pocket is bold (red), and its lid is dashed. A central problem in polymer physics and molecular biology is the reconfiguration of large molecules (modeled as polygons) such...
Kinodynamic Motion Planning on Roadmaps in Dynamic Environments (2008)
Abstract — In this paper we present a new method for kinodynamic motion planning in environments that contain both static and moving obstacles. We present an efficient twostage approach: in the...
REALIZING PARTITIONS RESPECTING FULL AND PARTIAL ORDER INFORMATION (2008)
Erik Demaine, Jeff Erickson, Danny Krizanć, Henk Meijer, Pat Morin, Mark Overmars, ...
Abstract. For n ∈ , we consider the problem of partitioning the interval [0, n) into k subintervals of positive integer lengths ℓ1,..., ℓk such that the lengths satisfy a set of simple...
Realizing Partitions Respecting Full and Partial Order Information Abstract (2008)
Erik D. Demaine, Jeff Erickson, Henk Meijer, Pat Morin, Mark Overmars, Sue Whitesides
For n ∈ N, we consider the problem of partitioning the interval [0, n) into k subintervals of positive integer lengths ℓ1,..., ℓk such that the lengths satisfy a set of simple constraints of...
Realizing Partitions Respecting Full and Partial Order Information (2008)
Erik Demaine, Jeff Erickson, Danny Krizanć, Henk Meijer, Pat Morin, Mark Overmars, ...
For n ∈ N, we consider the problem of partitioning the interval [0, n) into k subintervals of positive integer lengths ℓ1,..., ℓk such that the lengths satisfy a set of simple constraints of...
Efficient Path Planning in Changing Environments (2008)
Dennis Nieuwenhuisen, Jur Berg, Mark Overmars
Abstract — This paper addresses the problem of path planning in environments in which some of the obstacles can change their positions. It uses the popular PRM method for navigating a robot through...
Drs Joske, Houtkamp Dr, Martijn Emmerik, Prof Dr, Mark Overmars, Dr. Jelte Bos, ...
The effect of cybersickness on the affective appraisal of virtual environments E.D. van der Spek
March 25, 2005 8:15 WSPC/Guidelines chordsep SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS (2008)
Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, ...
∗Partially supported by DURSI 2001SGR00224, Acció Integrada UPC-McGill (DURSI2004) and
Pin Design for Part Feeding = Dept. of Industrial Eng. (2008)
Robert-paul Berretty, Mark Overmars
Abstract-- We consider a sensorless approach to feeding parts on a conveyor belt using pins (rigid barriers) to topple parts into desired orientations. Given the n-sided 2D convex projection of an...
March 25, 2005 14:14 WSPC/Guidelines chordsep SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS (2008)
Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, ...
∗Partially supported by DURSI 2001SGR00224, Acció Integrada UPC-McGill (DURSI2004) and
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),...
KEYWORDS Game design, Education, Game Maker. ABSTRACT GAME DESIGN IN EDUCATION (2008)
Computer games play a very important role in the life of most youth. Games offer many possibilities in education. Various people have studied the use of existing games or specially designed...
REALIZING PARTITIONS RESPECTING FULL AND PARTIAL ORDER INFORMATION (2008)
Erik Demaine, Jeff Erickson, Danny Krizanć, Henk Meijer, Pat Morin, Mark Overmars, ...
Abstract. For n ∈ �, we consider the problem of partitioning the interval [0, n) into k subintervals of positive integer lengths ℓ1,..., ℓk such that the lengths satisfy a set of simple...
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),...
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....
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),...
Dynamic Motion Planning in Low Obstacle Density Environments (2008)
Robert-paul Berretty, Mark Overmars
A fundamental task for an autonomous robot is to plan its own motions. Exact approaches to the solution of this motion planning problem suffer from high worst-case running times. The weak and...
Pankaj K. Agarwal, Mark Overmars, Micha Sharir
Let S be a set of n points in R2. Given an integer 1 ≤ k ≤ n, we wish to find a maximally separated subset I ⊆ S of size k; this is a subset for which the minimum among the � � k 2 pairwise...
Realizing Partitions Respecting Full and Partial Order Information Abstract (2008)
Erik D. Demaine, Jeff Erickson, Henk Meijer, Pat Morin, Mark Overmars, Sue Whitesides
For n ∈ N, we consider the problem of partitioning the interval [0,n) into k subintervals of positive integer lengths ℓ1,...,ℓk such that the lengths satisfy a set of simple constraints of the...
COMPUTING MAXIMALLY SEPARATED SETS IN THE PLANE ∗ (2008)
Pankaj K. Agarwal, Mark Overmars, Micha Sharir
Abstract. Let S be a set of n points in R2. Given an integer 1 ≤ k ≤ n, we wish to find a maximally separated subset I ⊆ S of size k; this is a subset for which the minimum among the �k � 2...
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....
Boudewijn Asberg, Gregoria Blanco, Jesus Garcia-lopez, Mark Overmars, Godfried Toussaint, Gordon Wilfong, ...
We study the feasibility of design for a layer-deposition manufacturing process called stereolithography which works by controlling a vertical laser beam which when targeted on a photocurable liquid...
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...
Oswin Aichholzerf, Vida Dujmovid, Mark Overmars, Carmen Cortes, Jeff Erickson, ...
jeffecs.uiuc.edu
Flipturning Polygons* (Extended abstract) (2007)
Oswin Aichholzer, Carmen Corts, Erik D. Demaine, Vida Dujmovi, Jeff Ericksonll, Henk Meijer, ...
Figure 1. A flipturn. The pocket is bold (red), and its lid is dashed. A central problem in polymer physics and molecular biology is the reconfiguration of large molecules (modeled as polygons) such...
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...
Greg Aloupis, Erik D. Demaine, Stefan Langerman, Henk Meijer, Mark Overmars, Godfried T. Toussaint
Given a planar polygon (or chain) with a list of edges
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...
. Rijksuniv..ersiteit Utrecht (2007)
Vakgrep Nformatica, Mark Overmars, Mark Overmars, Mark Overmars, Bertha Scholten, Bertha Scholten, ...
Sets withou t empty convex 6-gons
Reaching a Goal with Directional Uncertainty (2007)
Mark Berg, Mark Berg, Mark Overmars, Mark Overmars, Micha Sharir, Micha Sharir, ...
Overmars 1
Mark Overmars, Anil Rao, Otfried Schwarzkopf, Chantal Wentink
A familiar task in industrial applications is grasping an object to constrain its motions. When the external forces and torques acting on the object are uncertain or varying, form-closure grasps are...
Greg Aloupis, Erik D. Demaine, Stefan Langerman, Henk Meijer, Mark Overmars, Godfried T. Toussaint
Given a planar polygon (or chain) with a list of edges fe 1; e 2; e 3; : : :; e n 1; e n g, we examine the eect of several operations that permute this edge list, resulting in the formation of a new...
Boudewijn Asberg, Gregoria Blanco, Jesus Garcia-lopez, Mark Overmars, Godfried Toussaint, Gordon Wilfong, ...
We study the feasibility of design for a layer-deposition manufacturing process called stereolithography which works by controlling a vertical laser beam which when targeted on a photocurable liquid...
Dynamic Motion Planning in Low Obstacle Density Environments (2007)
Robert-paul Berretty, Mark Overmars
A fundamental task for an autonomous robot is to plan its own motions. Exact approaches to the solution of this motion planning problem suffer from high worst-case running times. The weak and...
Approximating Generalized Voronoi Diagrams (2007)
Jules Vleugels, Jules Vleugels, Jules Vleugels, Mark Overmars, Mark Overmars, Mark Overmars
Generalized Voronoi diagrams of objects are difficult to compute in a robust way, especially in higher dimensions. For a number of applications an approximation of the real diagram within some...
THE RECONSTRUCTION OF DYNAMIC DATA STRUCTURES (2007)
Michiel Smid, Mark Overmars, Vakgroep Informatica, Leen Torenvliet, Leen Torenvliet, ...
dynamic data structures
Oswin Aichholzer, Erik D. Demaine, Je Erickson, Ferran Hurtado, Mark Overmars, Michael Soss, ...
We prove that there is a motion from any convex polygon to any convex polygon with the same counterclockwise sequence of edge lengths, that preserves the lengths of the edges, and keeps the polygon...
Preprocessing Chains for Dihedral Rotations is Difficult (2007)
Michael Soss, Jeff Erickson, Mark Overmars
This draft was last touched on September 14, 2001. We examine a computational geometric problem concerning the structure of polymers. We model a polymer as a polygonal chain in three dimensions. Each...
On R-trees with low query complexity (2007)
Mark Overmars, Mark De Berg, Mark De Berg, Joachim Gudmundsson, Joachim Gudmundsson, Mikael Hammar, ...
######## # The R-tree is a well-known bounding-volume hierarchythat is suitable for storing geometric data on secondary memory. Unfortunately, no good analysis of its query time exists. We describe a...
Flat-State Connectivity of Linkages under Dihedral Motions (2007)
Greg Aloupis, Erik D. Demaine, Vida Dujmovic, Jeff Erickson, Stefan Langerman, Henk Meijer, ...
We explore which classes of linkages have the property that each pair of their at states|that is, their embeddings in R without self-intersection|can be connected by a continuous dihedral motion that...
Models and Motion Planning (2007)
Mark De Berg, Matthew J. Katz, Mark Overmars, Jules Vleugels
We study the consequences of two of the realistic input models proposed in the literature, namely unclutteredness and small simplecover complexity, for the motion planning problem. We show that the...
The Corridor Map Method: Real-Time High-Quality Path Planning (2007)
Roland Geraerts, Mark Overmars
A central problem in robotics is planning a collision-free path for a moving object in an environment with obstacles. Contemporary applications require a path planner that is fast (to ensure...
Computing Shortest Safe Path amidst Growing Discs in the Plane (2007)
Van Den Berg, Jur, Overmars, Mark
In this paper we discuss the problem of planning safe paths amidst unpredictably moving obstacles in the plane. Given the initial positions and the maximal velocities of the moving obstacles, the...
The Game Maker's Apprentice : Game Development for Beginners (2006)
Habgood, Jacob, Overmars, Mark
978-1-59059-615-9
Enric Cervera, François Chaumette, Henrik Christensen, Rüdiger Dillmann, Etienne Dombre, ...
List of contributors This report is the result of a workshop, a number of meetings —formal and informal—, discussions — physical or email-based—, and information gathering, either obtained...
Planning the shortest safe path amidst unpredictably moving obstacles (2006)
Summary. In this paper we discuss the problem of planning safe paths amidst unpredictably moving obstacles in the plane. Given the initial positions and the maximal velocities of the moving...
Clearance based path optimization for motion planning (2004)
Roland Geraerts, Mark Overmars
Many motion planning techniques, like the probabilistic roadmap method (PRM), generate low quality paths. In this paper, we will study a number of di#erent quality criteria on paths in particular...
Clearance based path optimization for motion planning (2004)
Roland Geraerts, Roland Geraerts, Mark Overmars, Mark Overmars
Many motion planning techniques, like the probabilistic roadmap method (PRM), generate low quality paths. In this paper, we will study a number of different quality criteria on paths in particular...
Separating point sets in polygonal environments (2004)
Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, ...
We consider the separability of two point sets inside a polygon by means of chords or geodesic lines. Specifically, given a set of red points and a set of blue points in the interior of a polygon, we...
Automatic generation of camera motion to track a moving guide (2004)
Manually following a moving object through a cluttered virtual environment can be challenging for the user. Instead, one would typically rather focus on watching the object and its environment. In...
Separating point sets in polygonal environments (2004)
Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, ...
We consider the separability of two point sets inside a polygon by means of chords or geodesic lines. Specifically, given a set of red points and a set of blue points in the interior of a polygon, we...
Clearance based path optimization for motion planning (2004)
Roland Geraerts, Roland Geraerts, Mark Overmars, Mark Overmars
Many motion planning techniques, like the probabilistic roadmap method (PRM), generate low quality paths. In this paper, we will study a number of different quality criteria on paths in particular...
Separating point sets in polygonal environments (2004)
Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, ...
We consider the separability of two point sets inside a polygon by means of chords or geodesic lines. Specifically, given a set of red points and a set of blue points in the interior of a polygon, we...
Finding sets of points without empty convex 6-gons (2003)
Mark H. Overmars, Mark Overmars
Erdös asked whether every large enough set of points in general position in the plane contains six points that form a convex 6-gon without any points from the set in its interior. In this note we...
Pankaj K. Agarwal, Mark Overmars, Micha Sharir
Given an integer 1 n, we wish to find a maximally separated subset I S of size k; this is a subset for which the minimum among the pairwise distances between its points is as large as possible. The...
Preprocessing Chains for Fast Dihedral Rotations Is Hard or Even Impossible (2002)
Soss, Michael, Erickson, Jeff, Overmars, Mark
We examine a computational geometric problem concerning the structure of polymers. We model a polymer as a polygonal chain in three dimensions. Each edge splits the polymer into two subchains, and a...
Flat-state connectivity of linkages under dihedral motions (2002)
Greg Aloupis, Erik D. Demaine, Vida Dujmović, Jeff Erickson, Stefan Langerman, Henk Meijer, ...
Abstract. We explore which classes of linkages have the property that each pair of their flat states—that is, their embeddings in R 2 without self-intersection—can be connected by a continuous...
Preprocessing chains for fast dihedral rotations is hard or even impossible (2002)
Michael Soss, Je Erickson, Mark Overmars
We examine a computational geometric problem concerning the structure of polymers. We model a polymer as a polygonal chain in three dimensions. Each edge splits the polymer into two subchains, and a...
On R-trees with low stabbing number (2002)
Mark De Berg, Joachim Gudmundsson, Mikael Hammar, Mark Overmars
. The R-tree is a well-known bounding-volume hierarchy that is suitable for storing geometric data on secondary memory. Unfortunately, no good analysis of its query time exists. We describe a new...
Computing Signed Permutations of Polygons (2002)
Greg Aloupis Prosenjit, Erik D. Demaine, Stefan Langerman, Henk Meijer, Mark Overmars, Godfried T. Toussaint
Given a planar polygon (or chain) with a list of edges fe 1 ; e 2 ; e 3 ; : : : ; e n 1 ; e n g, we examine the eect of several operations that permute this edge list, resulting in the formation of a...
Preprocessing chains for fast dihedral rotations is hard or even impossible (2002)
Michael Soss, Jeff Erickson, Mark Overmars
We examine a computational geometric problem concerning the structure of polymers. We model a polymer as a polygonal chain in three dimensions. Each edge splits the polymer into two subchains, and a...
Flat-state connectivity of linkages under dihedral motions (2002)
Greg Aloupis, Erik D. Demaine, Jeff Erickson, Stefan Langerman, Henk Meijer, Mark Overmars, ...
Abstract. We explore which classes of linkages have the property that each pair of their flat states--that is, their embeddings in R2 without self-intersection--can be connected by a continuous...
Preprocessing chains for fast dihedral rotations is hard or even impossible (2002)
Michael Soss, Jeff Erickson, Mark Overmars
We examine a computational geometric problem concerning the structure of polymers. We model a polymer as a polygonal chain in three dimensions. Each edge splits the polymer into two subchains, and a...
Flat-State Connectivity of Linkages under Dihedral Motions (2002)
Greg Aloupis, Erik D. Demaine, Vida Dujmovic, Jeff Erickson, Stefan Langerman, Henk Meijer, ...
We explore which classes of linkages have the property that each pair of their at states|that is, their embeddings in R without self-intersection|can be connected by a continuous dihedral motion that...
Aichholzer, Oswin, Cortes, Carmen, Demaine, Erik D., Dujmovic, Vida, Erickson, Jeff, Meijer, Henk, ...
A flipturn is an operation that transforms a nonconvex simple polygon into another simple polygon, by rotating a concavity 180 degrees around the midpoint of its bounding convex hull edge. Joss and...
Reconfiguring Convex Polygons (2000)
Oswin Aichholzer Erik, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, Mark Overmars, Michael A. Soss, ...
. We prove that there is a motion from any convex polygon to any convex polygon with the same counterclockwise sequence of edge lengths, that preserves the lengths of the edges, and keeps the polygon...
Reconfiguring Convex Polygons (2000)
Oswin Aichholzer, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, Mark Overmars, Michael A. Soss, ...
. We prove that there is a motion from any convex polygon to any convex polygon with the same counterclockwise sequence of edge lengths, that preserves the lengths of the edges, and keeps the polygon...
New Visibility Partitions with Applications in Affine Pattern Matching (1999)
Michiel Hagedoorn, Mark Overmars, Remco C. Veltkamp
Visibility partitions play an important role in computer vision and pattern matching. A visibility partition is formed by regions in which the combinatorial structure of the visibility is constant....
Guarding Scenes against Invasive Hypercubes (1998)
Mark De Berg, Haggai David, Matthew J. Katz, Mark Overmars, Jules Vleugels
A set of points G is a -guarding set for a set of objects O, if any hypercube not containing a point from G in its interior intersects at most objects of O. This definition underlies a new input...
Unfolding Some Classes of Orthogonal Polyhedra (1998)
Therese Biedl, Erik Demaine, Martin Demaine, Anna Lubiw, Mark Overmars, Joseph O'Rourke, ...
In this paper, we study unfoldings of orthogonal polyhedra. More precisely, we define two special classes of orthogonal polyhedra, orthostacks and orthotubes, and show how to generate unfoldings by...
Shape Tolerance in Feeding and Fixturing (1998)
Jingliang Chen, Ken Goldberg, Mark Overmars, Dan Halperin, Karl Bohringer, Yan Zhuang
Parts are not ideal. Designers and machinists cope with variation in part shape by specifying tolerance zones around a nominal part geometry: all parts that fit within the zone form a tolerance...
Algorithms for fixture design (1997)
Chantal Wentink, Mark Overmars
Manufacturing and assembly processes often require objects to be held in such a way that they can resist all external wrenches. The problem of "fixture planning " is to compute, for...
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...
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...
Analysis of probabilistic roadmaps for path planning (1996)
Jean-claude Latombe, Mark Overmars, Lydia Kavraki, Lydia Kavraki
1
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...
Immobilizing polygons against a wall (1995)
Mark Overmars, Anil Rao, Otfried Schwarzkopf, Chantal Wentink
A familiar task in industrial applications is grasping an object to constrain its motions. When the external forces and torques acting on the object are uncertain or varying, form-closure grasps are...
Reaching a goal with directional uncertainty (1994)
De Berg, Mark, Guibas, Leonidas, Halperin, Dan, Schwarzkopf, Otfried, Sharir, Micha, Teillaud, Monique, ...
Disponible dans les fichiers attachés à ce document
Reaching a goal with directional uncertainty (1994)
De Berg, Mark, Guibas, Leonidas, Halperin, Dan, Schwarzkopf, Otfried, Sharir, Micha, Teillaud, Monique, ...
Disponible dans les fichiers attachés à ce document
Computing the angularity tolerance (1994)
Mark De Berg, Henk Meijer, Mark Overmars, Gordon Wilfong
In computational metrology one needs to compute whether an object satisfies specifications of shape within an acceptable tolerance. To this end positions on the object are measured, resulting in a...
New results on binary space partitions in the plane (1994)
Mark De Berg, Marko De Groot, Mark Overmars
We prove the existence of linear size binary space partitions for sets of objects in the plane under certain conditions. In particular, we construct linear size binary space partitions for sets of...
Reaching a Goal with Directional Uncertainty (1994)
Monique Teillaud, Mark De Berg, Mark De Berg, Leonidas Guibas, Leonidas Guibas, Dan Halperin, ...
: We study two problems related to planar motion planning for robots with imperfect control, where, if the robot starts a linear movement in a certain commanded direction, we only know that its...
Prosenjit Bose, Leonidas Guibas, Anna Lubiw, Mark Overmars, Diane Souvaine, Jorge Urrutia
Given three angles summing to 2, given n points in the plane and a tripartition k1 + k2 + k3 = n, we can tripartition the plane into three wedges of the given angles so that the i-th wedge contains...
Prosenjit Bose, Leonidas Guibas, Anna Lubiw, Mark Overmars, Diane Souvaine, Jorge Urrutia
Given three angles summing to 2pi, given n points in the plane and a tripartition k 1 + k 2 + k 3 = n, we can tripartition the plane into three wedges of the given angles so that the i-th wedge...
Feasibility of Design in Stereolithography (1993)
Boudewijn Asberg, Gregoria Blanco, Prosenjit Bose, Jesus Garcia-lopez, Mark Overmars, ...
We study the feasibility of design for a layer-deposition manufacturing process called stereolithography which works by controlling a vertical laser beam which when targeted on a photocurable liquid...
Prosenjit Bose, Leonidas Guibas, Anna Lubiw, Mark Overmars, Diane Souvaine, Jorge Urrutia
Given three angles summing to 2ß, given n points in the plane and a tripartition k 1 + k 2 + k 3 = n, we can tripartition the plane into three wedges of the given angles so that the i-th wedge...
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...
Finding minimum area k-gons (1992)
Mark Overmars, Günter Rote, Gerhard Woeginger
Given a set P of n points in the plane and a number k, we want to find a polygon C with vertices in P of minimum area that satisfies one of the following properties: (1) C is a convex k-gon, (2) C is...