David Bremner, Ferran Hurtado, Suneeta Ramaswami, Vera Sacristán
Abstract. In this paper we give upper and lower bounds on the number of Steiner points required to construct a strictly convex quadrilateral mesh for a planar point set. In particular, we show that...
A Branch and Cut Algorithm for the Halfspace Depth Problem (2009)
The concept of \emph{data depth} in non-parametric multivariate descriptive statistics is the generalization of the univariate rank method to multivariate data. \emph{Halfspace depth} is a measure of...
Games on Triangulations (2009)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Abstract. We analyze several perfect-information combinatorial games played on planar triangulations. We introduce three broad categories of such games—constructing, transforming, and marking...
Geometric Games on Triangulations Extended Abstract (2009)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Let S be a set of n points in the plane, which we assume to be in general position, i.e., no three points of S lie on the same line. A triangulation of S is a simplicial decomposition of its convex...
Geometric Games on Triangulations Extended Abstract (2009)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
1 Introduction Let S be a set of n points in the plane, which we assume to be in general position, i.e., no threepoints of S lie on the same line. A triangulation of S is a simplicial decomposition...
◮ The breakdown point of an estimator is the fraction of data that must be moved to infinity before the estimator is also moved to infinity. ◮ The breakdown point of the mean is 1 n destroy the...
SYMMETRIC MATROID POLYTOPES AND THEIR GENERATION (2008)
Jürgen Bokowski, David Bremner, Gábor Gévay
Abstract. Matroid polytopes form an intermediate structure useful in searching for realizable convex spheres. In this article we present a class of self-polar 3-spheres that motivated research in the...
Edge-Graph Diameter Bounds for Convex Polytopes with Few Facets (2008)
We show that the edge graph of a 6-dimensional polytope with 12 facets has diameter at most 6, thus verifying the d-step conjecture of Klee and Walkup in the case of d=6. This implies that for all...
Playing with Triangulations (2008)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Abstract. We analyze several perfect-information combinatorial games played on planar triangulations. We introduce three broad categories of such games: constructing, transforming, and marking...
Geometric Games on Triangulations Extended Abstract (2008)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Let S be a set of n points in the plane, which we assume to be in general position, i.e., no three points of S lie on the same line. A triangulation of S is a simplicial decomposition of its convex...
Pankaj K. Agarwal, Its Relatives In, B. Chazelle, J. E. Goodman, R. Pollack, Advances In Discrete, ...
[1] P. K. Agarwal. Partitioning arrangements of lines II: Applications. Discrete & Computational
Necklaces, Convolutions, and X + Y (2008)
David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, ...
Abstract. We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is...
Computing the Tool Path of an Externally Monotone Polygon in Linear Time ∗ (2008)
Prosenjit Bose, David Bremner, Diane Souvaine
A Numerically-Controlled (NC) machine typically consists of a worktable and a spindle (or cutter) with several axes of freedom for positioning the tool. In this paper,
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries ⋆ (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Abstract. Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R ∪ B comes...
Necklaces, Convolutions, and X + Y (2008)
David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, ...
We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is measured...
Necklaces, Convolutions, and X + Y (2008)
David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, ...
Abstract. We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries ⋆ (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Abstract. Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R ∪ B comes...
OUTPUT-SENSITIVE ALGORITHMS FOR COMPUTING NEAREST-NEIGHBOUR DECISION BOUNDARIES ∗ (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
ABSTRACT. Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R ∪ B comes...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R B comes from R...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R [ B comes from R...
Small Convex Quadrangulations of Point Sets (2008)
David Bremner, Ferran Hurtado, Suneeta Ramaswami, Vera Sacristan
In this paper, we give upper and lower bounds on the number of Steiner points required to construct a strictly convex quadrilateral mesh for a planar point set. In particular, we show that 3b 2 c...
Games on Triangulations (2008)
Oswin Aichholzer David, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
We analyze several perfect-information combinatorial games played on planar triangulations. We introduce three broad categories of such games---constructing, transforming, and marking...
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2008)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R ∪ B comes from...
Inner diagonals of convex polytopes (Extended Abstract) (2007)
David Bremner and Victor Klee # 1 Introduction An inner diagonal of a polytope P is a segment that joins two vertices of P and that lies, except for its ends, in P 's relative interior. For 1 #...
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Computer Science Department, University of Illinois,
Playing with Triangulations (2007)
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
Abstract. We analyze several perfect-information combinatorial games played on planar triangulations. We introduce three broad categories of such games: constructing, transforming, and marking...
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
9 1
Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, ...
9 1
Upper and Lower Bounds for Strictly Convex Quadrilateral Meshes of Point Sets (2007)
David Bremner, Ferran Hurtado, Suneeta Ramaswami
In this paper, we give upper and lower bounds on the number of Steiner points required to construct a strictly convex quadrilateral mesh for a planar point set. In particular, we show that 3b n 2 c...
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...
Mark De Berg, David Bremner, Suneeta Ramaswami, Gordon Wilfong
We study the problem of determining whether a manufactured disc of certain radius r is within tolerance. More precisely, we present algorithms that, given a set of n probe points on the surface of...
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...
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...
Oswin Aichholzer, David Bremner, Erik D. Demaine, Henk Meijer, Michael Soss
We explore a problem suggested by Brian Hayes in 1998: what proteins in the twodimensional hydrophilic-hydrophobic (H-P) model have unique optimal foldings? In particular, we prove that there are...
Worksheet 1: Degree Sequences (2007)
I will give the exercises a (mostly subjective) difficulty rating from H to \Upsilon\Upsilon\Upsilon, with \Sigma marking open problems. We will follow (loosely) the text Modern Graph Theory [Bol98],
Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries (2007)
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R B comes from R...
David Bremner, Erik Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, ...
Computer Science Department, University of Illinois,
Recovering Lines with Fixed Linear Probes (Extended Abstract) (2007)
Mark De Berg, Jit Bose, David Bremner, William Evans, Lata Narayanan
Mark de Berg Jit Bose David Bremner William Evans Lata Narayanan 1 Introduction Suppose the only access we have to an arrangement of n input lines is to "probe" the arrangement with...
The complexity of the envelope of line and plane arrangements (2007)
Bremner, David, Deza, Antoine, Xie, Feng
A facet of an hyperplane arrangement is called external if it belongs to exactly one bounded cell. The set of all external facets forms the envelope of the arrangement. The number of external facets...
Polyhedral representation conversion up to symmetries (2007)
Bremner, David, Sikiric, Mathieu Dutour, Schuermann, Achill
We give a short survey on computational techniques which can be used to solve the representation conversion problem for polyhedra up to symmetries. We in particular discuss decomposition methods,...
The complexity of the envelope of line and plane arrangements (2007)
David Bremner, Antoine Deza, Feng Xie, David Bremner, Antoine Deza, Feng Xie
The complexity of the envelope
Outputsensitive algorithms for Tukey depth and related problems, Submitted (2006)
David Bremner, Stefan Langerman, Dan Chen, Pat Morin, John Iacono
ABSTRACT. The Tukey depth (Tukey 1975) of a point p with respect to a finite set S of points is the minimum number of elements of S contained in any closed halfspace that contains p. Algorithms for...
Outputsensitive algorithms for Tukey depth and related problems, Submitted (2006)
David Bremner, Dan Chen, John Iacono, Stefan Langerman, Pat Morin
ABSTRACT. The Tukey depth (Tukey 1975) of a point p with respect to a finite set S of points is the minimum number of elements of S contained in any closed halfspace that contains p. Algorithms for...
Barrie Bickle, Al Bieber, George Binns, Valerie Block, Harvey Boyd, David Bremmer, ...
Abstract: This standard contains the minimum requirements for door systems and door system operation on new and rebuilt rail passenger cars. Key Words: doors, door systems, emergency evacuation...
Sufficiently Fat Polyhedra are not 2-castable (2002)
Bremner, David, Golynski, Alexander
In this note we consider the problem of manufacturing a convex polyhedral object via casting. We consider a generalization of the sand casting process where the object is manufactured by gluing...
Small Strictly Convex Quadrilateral Meshes of Point Sets (2002)
Bremner, David, Hurtado, Ferran, Ramaswami, Suneeta, Sacristan, Vera
In this paper, we give upper and lower bounds on the number of Steiner points required to construct a strictly convex quadrilateral mesh for a planar point set. In particular, we show that...
Long Proteins with Unique Optimal Foldings in the H-P Model (2002)
Aichholzer, Oswin, Bremner, David, Demaine, Erik D., Meijer, Henk, Sacristán, Vera, Soss, Michael
It is widely accepted that (1) the natural or folded state of proteins is a global energy minimum, and (2) in most cases proteins fold to a unique state determined by their amino acid sequence. The...
Computing Constrained Minimum-Width Annuli of Point Sets (2000)
Mark De Berg, Prosenjit Bose, David Bremner, Suneeta Ramaswami, Gordon Wilfong
We study the problem of determining whether a manufactured disc of certain radius r is within tolerance. More precisely, we present algorithms that, given a set of n probe points on the surface of...
Recovering Lines with Fixed Linear Probes (1998)
Mark De Berg, Jit Bose, David Bremner, William Evans, Lata Narayanan
This paper addresses the problem of fixed probes; in our setting the locations of the probes must be chosen before the input is examined. In the case of intersection probes, we show that for each...
Point Visibility Graphs and O-Convex Cover (1998)
David Bremner, Thomas Shermer, Let O
A visibility relation can be viewed as a graph: the uncountable graph of a visibility relationship between points in a polygon P is called the point visibility graph (PVG) of P . In this paper we...
Inner Diagonals Of Convex Polytopes (1998)
. An inner diagonal of a polytope P is a segment that joins two vertices of P and that lies, except for its ends, in P 's relative interior. The paper's main results are as follows: (a)...
Primal-Dual Methods for Vertex and Facet Enumeration (1998)
David Bremner, Komei Fukuda, Ambros Marzetta
Every convex polytope can be represented as the intersection of a finite set of halfspaces and as the convex hull of its vertices. Transforming from the halfspace (respectively vertex) to the vertex...
How good are convex hull algorithms (1997)
A convex polytope is the bounded intersection of finite set H of halfspaces. A classic theorem of convexity theory is that every convex polyhedron can be expressed as the convex hull of its set V of...
How good are convex hull algorithms (1997)
David Avis, David Bremner, Raimund Seidel, Fachberich Informatik
A convex polytope P can be specified in two ways: as the convex hull of the vertex set V of P, or as the intersection of the set H of its facet-inducing halfspaces. The vertex enumeration problem is...
How Good are Convex Hull Algorithms? (1997)
David Avis, David Bremner, Raimund Seidel, Fachberich Informatik
A convex polytope P can be specified in two ways: as the convex hull of the vertex set V of P , or as the intersection of the set H of its facet-inducing halfspaces. The vertex enumeration problem is...
School Of, David Avis, David Bremner, Raimund Seidel, Fachberich Informatik
A convex polytope P can be specified in two ways: as the convex hull of the vertex set V of P , or as the intersection of the set H of its facet-inducing halfspaces. The vertex enumeration problem is...
David Avis, Raimund Seidel Y, David Bremner, Fachberich Informatik
A convex polytope P can be speci ed in two ways: as the convex hull of the vertex set V of P,orastheintersection of the set H of its facet-inducing halfspaces. The vertex enumeration problem is to...
All Convex Polyhedra can be Clamped with Parallel Jaw Grippers (1996)
Prosenjit Bose, David Bremner, Godfried Toussaint
We study various classes of polyhedra that can be clamped usingparallel jaw grippers. We show that all n-vertex convex polyhedra can be clamped regardless of the gripper size and present an O(n + k)...
Incremental Convex Hull Algorithms Are Not Output Sensitive (1996)
A polytope is the bounded intersection of a finite set of halfspaces of R d . Every polytope can also be represented as the convex hull conv V of its vertices (or extreme points) V . The convex hull...
Computing Constrained Minimum-Width Annuli of Point Sets (1996)
Mark De Berg, Prosenjit Bose, David Bremner, Suneeta Ramaswami, Gordon Wilfong
. We study the problem of determining whether a manufactured disc of certain radius r is within tolerance. More precisely, we present algorithms that, given a set of n probe points on the surface of...
All convex polyhedra can be clamped with parallel jaw grippers (1994)
Prosenjit Bose, David Bremner, Godfried Toussaint
Abstract We study various classes of polyhedra that can be clamped using parallel jaw grippers. We show that all n-vertex convex polyhedra can be clamped regardless of the gripper size and present an...
All convex polyhedra can be clamped with parallel jaw grippers (1994)
Prosenjit Bose, David Bremner, Godfried Toussaint
We study various classes of polyhedra that can be clamped using parallel jaw grippers. We show that all n-vertex convex polyhedra can be clamped regardless of the gripper size and present an O(n + k)...
All convex polyhedra can be clamped with parallel jaw grippers (1994)
David Bremner, Godfried Toussaint
We study various classes of polyhedra that can be clamped using parallel jaw grippers. We show that all n-vertex convex polyhedra can be clamped regardless of the gripper size and present an O(n+k)...
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...
The industries of Scotland, their rise, progress, and present condition. (1869)
2 p.l., [iii]-viii, 535 p.
All Convex Polyhedra can be Clamped with Parallel Jaw Grippers
Prosenjit Bose, David Bremner, Godfried Toussaint
We study various classes of polyhedra that can be clamped using parallel jaw grippers. We show that all n-vertex convex polyhedra can be clamped regardless of the gripper size and present an O(n + k)...