Straight Skeletons of Three-Dimensional Polyhedra (2009)
Gill Barequet, Michael T. Goodrich, Amir Vaxman
Abstract. This paper studies the straight skeleton of polyhedra in three dimensions. We first address voxel-based polyhedra (polycubes), formed as the union of a collection of cubical (axis-aligned)...
554 An Upper Bound on the Number of Rectangulations of a Point Set ⋆ (2008)
Eyal Ackerman, Gill Barequet, Ron Y. Pinter
Abstract. We consider the number of different ways to divide a rectangle containing n noncorectilinear points into smaller rectangles by n non-intersecting axis-parallel segments, such that every...
Straight Skeletons of Three-Dimensional Polyhedra (2008)
Barequet, Gill, Eppstein, David, Goodrich, Michael T., Vaxman, Amir
This paper studies the straight skeleton of polyhedra in three dimensions. We first address voxel-based polyhedra (polycubes), formed as the union of a collection of cubical (axis-aligned) voxels. We...
A Bijection Between Permutations and Floorplans, and its Applications (2008)
Eyal Ackerman, Gill Barequet, Ron Y. Pinter
A floorplan represents the relative relations between modules on an integrated circuit. Floorplans are commonly classified as slicing, mosaic, or general. Separable and Baxter permutations are...
The Number of Guillotine Partitions in d Dimensions ∗ (2008)
Eyal Ackerman, Gill Barequet, Ron Y. Pinter, Dan Romik
Guillotine partitions play an important role in many research areas and application domains, e.g., computational geometry, computer graphics, integrated circuit layout, and solid modeling, to mention...
Maximizing the Area of an Axially-Symmetric Polygon Inscribed by a Simple Polygon (2008)
In this paper we solve the following optimization problem: Given a simple polygon P, what is the maximum-area polygon that is axially symmetric and is contained by P? We propose an algorithm for...
Computing the Minimum Enclosing Circle of a Set of Planar Curves (2008)
Gill Barequet, Gershon Elber, Myung-soo Kim
The problem of computing the minimum enclosing circle of a point set is a classical problem in computational geometry. It is known to be an LP-type problem, hence it has a very efficient algorithm...
Polygon Reconstruction from Line Cross-Sections ∗ (2008)
Avishay Sidlesky, Gill Barequet, Craig Gotsman
We study the following geometric probing problem: Reconstruct a planar polygon from its intersections with a collection of arbitrarily-oriented “cutting ” lines. We propose an algorithm which...
Graphics, and Image Processing, 44(1):1–29, 1988. (2008)
M. Alexa, J. Behr, D. Cohen-or, S. Fleishman, D. Levin, Rajit L. Bajaj, ...
based contour interpolation. In Proc. 14th Symp. Discrete Algorithms, pages
Esther M. Arkin, Gill Barequet
Algorithms for Two-Box Covering We study the problem of covering a set of points or polyhedra in ℜ 3 with two axis-aligned boxes in order to minimize a function of the measures of the two boxes,...
Gill Barequet, Micha Moffie, Günter Rote
Using numerical methods, we analyze the growth in the number of polyominoes on a twisted cylinder as the number of cells increases. These polyominoes are related to classical polyominoes (connected...
Two-Dimensional Visibility Charts for Continuous Curves (2008)
Gershon Elber Robert, Robert Sayegh, Gill Barequet, Ralph R. Martin
This paper considers computation of visibility for twodimensional shapes whose boundaries are C continuous curves. We assume we are given a one-parameter family of candidate viewpoints, which may be...
Polygon Reconstruction from Line Cross-Sections (2008)
Avishay Sidlesky Gill, Gill Barequet, Craig Gotsman
We study the following geometric probing problem: Reconstruct a planar polygon from its intersections with a collection of arbitrarily-oriented "cutting" lines. We propose an algorithm...
Gill Barequet, Sariel Har-peled
)-time algorithm for computing a (1 + ")-approximation of the minimum-volume bounding box of n points in IR 3. We also present a simpler algorithm whose running time is O(n log n +...
Abstract---In this paper we present a new technique for partial surface and volume matching of images in three dimensions. In this problem we are given two objects in 3-space, each represented as a...
We present an algorithm for reconstructing a solid model from a series of planar cross-sections. In most previous works the layers are assumed to be independent: each layer is interpolated separately...
2-Point Site Voronoi Diagrams (2007)
Gill Barequet, Matthew T. Dickerson
. In this paper we investigate a new type of Voronoi diagrams in which every region is defined by a pair of point sites and some distance function from a point to two points. We analyze the...
Gill Barequet, Matthew T. Dickerson
A polygon annulus is the region contained in some outer polygon but not contained in an inner polygon. Typically, the outer and inner polygons are concentric scaled or oset copies of the same...
Gill Barequet, Danny Z. Chen, Ovidiu Daescu, Michael T. Goodrich, Jack Snoeyink
We present efficient algorithms for solving polygonal-path approximation problems in three and higher dimensions. Given an n-vertex polygonal curve P in IR
Shape Blending Blending polygonal shapes with di!erent topologies � (2007)
Tatiana Surazhsky, Vitaly Surazhsky, Gill Barequet, Ayellet Tal
In this paper, we propose a new method for morphing between two polygonal, possibly non-simply connected, shapes in the plane. The method is based on reconstructing an xy-monotone surface whose...
Communicated by J. Mitchell The 3sum problem represents a class of problems conjectured to require\Omega\Gamma n
SIAM J. DISCRETE MATH. c (2007)
Abstract. In this paper we show a lower bound for the generalization of Heilbronn's triangle problem to d dimensions; namely, we show that there exists a set S of n points in the d-dimensional...
Counting polyominoes on twisted cylinders (2005)
Gill Barequet, Micha Moffie, Ares Ribó, Günter Rote
We improve the lower bounds on Klarner’s constant, which describes the exponential growth rate of the number of polyominoes (connected subsets of grid squares) with a given number of squares. We...
On the number of rectangular partitions (2004)
Eyal Ackerman, Gill Barequet, Ron Y. Pinter
How many ways can a rectangle be partitioned into smaller ones? We study two variants of this problem: when the partitions are constrained to lie on n given points (no two of which are...
Drawing Planar Graphs with Large Vertices and Thick Edges (2004)
Gill Barequet, Michael T. Goodrich, Chris Riley
We consider the problem of representing size information in the edges and vertices of a planar graph. Such information can be used, for example, to depict a network of computers and information...
Contour interpolation by straight skeletons, Graphical Models (2004)
Gill Barequet, Michael T. Goodrich, Aya Levi-steiner, Dvir Steiner D
In this paper we present an efficient method for interpolating a piecewise-linear surface between two parallel slices, each consisting of an arbitrary number of (possibly nested) polygons that define...
Drawing graphs with large vertices and thick edges (2003)
Gill Barequet, Michael T. Goodrich, Chris Riley
Abstract. We consider the problem of representing size information in the edges and vertices of a planar graph. Such information can be used, for example, to depict a network of computers and...
$\omega$-Searchlight Obedient Graph Drawings (2001)
A drawing of a graph in the plane is $\omega$-searchlight obedient if every vertex of the graph is located on the centerline of some strip of width $\omega$, which does not contain any other vertex...
$\omega$-Searchlight Obedient Graph Drawings (2001)
A drawing of a graph in the plane is $\omega$-searchlight obedient if every vertex of the graph is located on the centerline of some strip of width $\omega$, which does not contain any other vertex...
$\omega$-Searchlight Obedient Graph Drawings (2001)
A drawing of a graph in the plane is $\omega$-searchlight obedient if every vertex of the graph is located on the centerline of some strip of width $\omega$, which does not contain any other vertex...
Eciently approximating the minimum-volume bounding box of a point set in three dimensions (2001)
Gill Barequet, Sariel Har-peled
We present an ecient O(n + 1="
Blending polygonal shapes with different topologies (2001)
Tatiana Surazhsky, Vitaly Surazhsky, Gill Barequet, Ayellet Tal
In this paper we propose a new method for morphing between two polygonal, possibly non-simply-connected, shapes in the plane. The method is based on reconstructing an xy-monotone surface whose...
Efficient perspective-accurate silhouette computation and applications (2001)
Mihai Pop, Christian A. Duncan, Gill Barequet, Michael T. Goodrich, Wenjing Huang
� � � � � �Æ � � � � � � � � � � � ��Æ � � � � � � � � �Æ � � � � � � � �Æ � � � � � � � � � � � �...
Eyal Ackerman, Gill Barequet, Ron Y. Pinter
We investigate the number of different ways in which a rectangle containing a set of n noncorectilinear points can be partitioned into smaller rectangles by n (non-intersecting) segments, such that...
The translationscale diagram for point-containing placements of a convex polygon (2000)
Gill Barequet, Matthew T. Dickerson
We present a diagram that captures containment information for scalable translations of a convex polygon. For a given polygon P and contact point q in a set S, the diagram parameterizes possible...
Geomnet: Geometric computing over the internet (1999)
Gill Barequet, Christian A. Duncan, T. Goodrich, Stina S. Bridgeman, Roberto Tamassia
GeomNet’s layered client-server architecture lets users perform distributed geometric computing over the Internet without having to download, install, and interface with software.
2-point site Voronoi diagrams (1999)
Gill Barequet, Matthew T. Dickerson, David S. Guertin
The purpose of the video segment is to visualize threedimensional surfaces, so-called the Voronoi surfaces of the 2-site distance functions described below. In order to build
Polygon-Containment and Translational Min-Hausdorff-Distance between . . . (1999)
.05> f(B). There exists a translation v 2 IR such that A + v ` B iff. there is a rotation of A around o that makes A contained in B. Given an arc I ae C, denote by p(I) the intersection between...
A Lower Bound for Heilbronn's Triangle Problem in d Dimensions (1999)
In this paper we show a lower bound for the generalization of Heilbronn's triangle problem to d dimensions, namely, we show that there exists a set S of n points in the d- dimensional unit cube...
Efficiently approximating the minimum-volume bounding box of a point set in three dimensions (1999)
Gill Barequet, Sariel Har-peled
We present an efficient O(n + 1/ε 4.5)-time algorithm for computing a (1 + ε)approximation of the minimum-volume bounding box of n points in R 3. We also present a simpler algorithm (for the same...
Gill Barequet, Sariel Har-peled
The 3sum problem represents a class of problems conjectured to require \Omega\Gamma n 2 ) time to solve, where n is the size of the input. Given two simple polygons P and Q in the plane, we show that...
RSVP: A Geometric Toolkit for Controlled Repair of Solid Models (1998)
Gill Barequet, Christian A. Duncan, Subodh Kumar
This paper presents a system and the associated algorithms for repairing the boundary representation of CAD models. Two types of errors are considered: topological errors, i.e., aggregate errors like...
Efficiently Approximating Polygonal Paths in Three and Higher Dimensions (1998)
Gill Barequet, Danny Z. Chen, Ovidiu Daescu, Michael T. Goodrich, Jack Snoeyink
We present efficient algorithms for solving polygonal-path approximation problems in three and higher dimensions. Given an n-vertex polygonal curve P in IR d , d 3, we approximate P by another...
Optimizing a Strip Separating Two Polygons (1998)
Gill Barequet, Barbara Wolfers
We consider the problem of finding a strip separating between two polygons, whose intersection with a third (convex) polygon is of maximum area. We present an optimal linear-time algorithm for...
Efficiently Approximating Polygonal Paths in Three and Higher Dimensions (1998)
Gill Barequet, Danny Z. Chen, Ovidiu Daescu, Michael T. Goodrich, Jack Snoeyink
We present efficient algorithms for solving polygonal -path approximation problems in three and higher dimensions. Given an n-vertex polygonal curve P in IR d , d 3, we approximate P by another...
Partial surface and volume matching in three dimensions (1997)
Abstract—In this paper we present a new technique for partial surface and volume matching of images in three dimensions. In this problem we are given two objects in 3-space, each represented as a...
Classical Computational Geometry in GeomNet (1997)
Gill Barequet, Stina S. Bridgeman, Christian A. Duncan, Michael T. Goodrich, Roberto Tamassia
In this paper we present GeomNet, a system for performing distributed geometric computing over the Internet. We also provide several examples of actual geometric algorithms that our system already...
Voronoi Diagrams for Polygon-Offset Distance Functions (1997)
Gill Barequet, Matthew T. Dickerson, Michael T. Goodrich
. In this paper we develop the concept of a polygon-offset distance function and show how to compute the respective nearest- and furthest-site Voronoi diagrams of point sites in the plane. We provide...
A Data Front-End for Layered Manufacturing (1997)
In this paper we describe a geometric software package which serves as a data front-end for rapid prototyping systems. This package can be customized for every layered-manufacturing technique. We...
A Data Front-End for Layered Manufacturing (1997)
In this paper we describe a geometric software package which serves as a data front-end for rapid prototyping systems. This package can be customized for every layered-manufacturing technique. We...
We describe an algorithm for repairing polyhedral CAD models that have errors in their B-REP. Errors like cracks, degeneracies, duplication, holes and overlaps are usually introduced in solid models...
Offset-Polygon Annulus Placement Problems (1997)
Gill Barequet, Amy J. Briggs, Matthew T. Dickerson, Michael T. Goodrich, Michael T
. In this paper we address several variants of the polygon annulus placement problem: given an input polygon P and a set S of points, find an optimal placement of P that maximizes the number of...
Partial surface matching by using directed footprints (1996)
In this paper we present a new technique for partial surface and volume matching of images in three dimensions. In this problem, we are given two objects in 3-space, each represented as a set of...
DCEL: A Polyhedral Database And Programming Environment (1996)
In this paper we describe the DCEL system: a geometric software package which implements a polyhedral programming environment. This package enables fast prototyping of geometric algorithms for...
On Triangulating Three-Dimensional Polygons (1996)
Gill Barequet, Matthew Dickerson, And David Eppstein
A three-dimensional polygon is triangulable if it has a non-self-intersecting triangulation which defines a simply-connected 2-manifold. We show that the problem of deciding whether a 3-dimensional...
History Consideration in Reconstructing Polyhedral Surfaces from Parallel Slices (1996)
Gill Barequet, Daniel Shapiro, Ayellet Tal
We introduce an algorithm for reconstructing a solid model given a series of planar cross-sections. The main contribution of this work is the use of knowledge obtained during the interpolation of...
Partial Surface Matching by Using Directed Footprints (1996)
this paper by the first author has been supported by the Israeli Ministry of Science and the Arts, Eshkol Grant 0562-1-94. Work by the second author has been supported by NSF Grants CCR-91-22103 and...
Optimizing a Corridor between Two Polygons with an Application to Polyhedral Interpolation (1996)
Gill Barequet, Barbara Wolfers
We consider the problem of finding a corridor (a separating strip) between two polygons, whose intersection with a third (convex) polygon is of maximum area. The application in mind is the...
On Triangulating Three-Dimensional Polygons (1996)
Gill Barequet, Matthew Dickerson, David Eppstein
A three-dimensional polygon is triangulable if it has a non-self-intersecting triangulation which defines a simply-connected 2-manifold. We show that the problem of deciding whether a 3D polygon is...
On Triangulating Three-Dimensional Polygons (1996)
Gill Barequet, Matthew Dickerson
A three-dimensional polygon is triangulable if it has a non-self-intersecting triangulation which defines a simply-connected 2-manifold. We show that the problem of deciding whether a 3D polygon is...
BOXTREE: Hierarchical Representation for Surfaces in 3D (1996)
Gill Barequet, Bernard Chazelle, Leonidas J. Guibas, Ayellet Tal
We introduce the boxtree, a versatile data structure for representing triangulated or meshed surfaces in 3D. A boxtree is a hierarchical structure of nested boxes that supports efficient ray tracing...
BOXTREE: A Hierarchical Representation for Surfaces in 3D (1996)
Gill Barequet, Bernard Chazelle, Leonidas J. Guibas, Ayellet Tal
We introduce the boxtree, a versatile data structure for representing triangulated or meshed surfaces in 3D. A boxtree is a hierarchical structure of nested boxes that supports efficient ray tracing...
Translating a Convex Polygon to Contain a Maximum Number of Points (Extended abstract) (1995)
G. Barequet, Gill Barequet, Matthew Dickerson, Petru Pau
Gill Barequet y Matthew Dickerson z Petru Pau x 1 Introduction Finding an optimal transformation of a region such that it contains (encloses) a given point set or subset is a problem that has...
Piecewise-Linear Interpolation between Polygonal Slices (1994)
In this paper we present a new technique for piecewiselinear surface reconstruction from a series of parallel polygonal cross-sections. This is an important problem in medical imaging, surface...
Partial Surface and Volume Matching in Three Dimensions (1994)
. In this paper we present a new technique for partial surface and volume matching of images in three dimensions. In this problem, we are given two objects in 3-space, each represented as a set of...
Partial Surface and Volume Matching in Three Dimensions (1994)
In this paper we present a new technique for partial surface and volume matching of images in three dimensions. In this problem we are given two objects in 3-space, each represented as a set of...
Piecewise-Linear Interpolation between Polygonal Slices (1994)
In this paper we present a new technique for piecewise-linear surface reconstruction from a series of parallel polygonal cross-sections. This is an important problem in medical imaging, surface...
Filling Gaps in the Boundary of a Polyhedron (1993)
In this paper we present an algorithm for detecting and repairing defects in the boundary of a polyhedron. These defects, usually caused by problems in CAD software, consist of small gaps bounded by...
A Duality between Small-Face Problems in Arrangements of Lines and Heilbronn-Type Problems
. Arrangements of lines in the plane and algorithms for computing extreme features of arrangements are a major topic in computational geometry. Theoretical bounds on the size of these features are...
Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions
Gill Barequet, Sariel Har-peled
We present an efficient randomized O(n log n+1=" 4:5 ) expected-time algorithm for computing an "-approximation of the minimum-volume bounding box of n points in IR 3 . We also present a...
Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions
Gill Barequet, Sariel Har-peled
We present an efficient O(n + 1=" 4:5 ) time algorithm for computing an (1+")-approximation of the minimum-volume bounding box of n points in IR 3 . We also present a simpler algorithm (for...
Offset-Polygon Annulus Placement Problems
Gill Barequet, Amy J. Briggs, Matthew T. Dickerson, Michael T. Goodrich
An offset-polygon annulus region is defined in terms of a polygon P and a distance ffi ? 0 (offset of P ). In this paper we solve several containment problems for polygon annulus regions with respect...
A Duality between Small-Face Problems in Arrangements of Lines and Heilbronn-Type Problems
In this paper we show a duality between small-face problems in arrangements (bounded in the unit square) and Heilbronn-type problems. We use probabilistic methods and some constructions for obtaining...