Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun, Micha Sharir
Abstract Let B be a set of n unit balls in R 3. We show that the combinatorial complexity of the space of lines in R 3 that avoid all the balls of B is O(n
The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains (2009)
Boris Aronov, Mark De Berg, Shripad Thite
Abstract. We prove tight bounds on the complexity of bisectors and Voronoi diagrams on so-called realistic terrains, under the geodesic distance. In particular, if n denotes the number of triangles...
Abstract Cost-Driven Octree Construction Schemes: An Experimental Study ∗ (2009)
Boris Aronov, Hervé Brönnimann
Many algorithmic problems are interesting to both theoreticians and practitioners, but in a different manner. While the theoreticians have traditionally focused on worst-case scenarios which is often...
Boris Aronov, Jacob E. Goodman, Richard Pollack, Rephael Wenger
Abstract Let S be a family of compact convex sets in Rd. Let D(S)be the largest diameter of any member of S. The family S is e-separated if, for every 0! k! d, any k of thesets can be separated from...
Boris Aronov, Franz Aurenhammer, Ferran Hurtado, Stefan Langerman, Carlos Seara, Shakhar Smorodinsky
Given a set P of points in the plane, a set of points Q is a weak ε-net with respect to a family of sets S (e.g., rectangles, disks, or convex sets) if every set of S containing ε|P | points...
1 Introduction Small Weak Epsilon Nets (2008)
Boris Aronov, Franz Aurenhammer, Ferran Hurtado, Stefan Langerman, Shakhar Smorodinsky, Carlos Seara
Let P be a set of n points in R 2. A point q (not
On the Union of ^-Round Objects in Three and Four Dimensions* (2008)
Boris Aronov, Alon Efrat, Vladlen Koltun, Micha Sharir
Abstract A compact body c in Rd is ^-round if for every point p 2
Sorting Similar Vectors (2008)
We show how to sort a sequence of k n-bit vectors presented as a list of singlebit changes between consecutive vectors, in O((n + k) log n) deterministic time. An application of this result to a...
Polytechnic University AND (2008)
Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun
Abstract. A closed solid body separates one point set from another if it contains the former and the closure of its complement contains the latter. We present a near-linear algorithm for deciding...
Sparse geometric graphs with small dilation (2008)
Aronov, Boris, De Berg, Mark, Cheong, Otfried, Gudmundsson, Joachim, Haverkort, Herman, Smid, Michiel, ...
Given a set S of n points in , and an integer k such that 0k
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...
Ray Shooting Amidst Fat Convex Polyhedra in 3-Space (2008)
Boris Aronov, Mark Berg, Chris Gray
We present a data structure for ray-shooting queries in a set of convex fat polyhedra of total complexity n in R 3. The data structure uses O(n 2+ε) storage and preprocessing time, and queries can...
Largest Subsets of Triangles in a Triangulation ∗ (2008)
Boris Aronov, Marc Kreveld, Maarten Löffler, Rodrigo I. Silveira
Given a triangulation of n points, with some triangles marked “good”, this paper discusses the problems of computing the largest-area connected set of good triangles that (i) is convex, (ii) is...
The Complexity of Diffuse Reflections in a Simple Polygon (2008)
Boris Aronov, Alan R. Davis, John Iacono, Albert Siu, Cheong Yu
Abstract. The complexity of the visibility region formed by a point light source after k diffuse reflections in a simple n-sided polygon is O(n 9), which is the first result polynomial in n, with no...
The Complexity of Diffuse Reflections in a Simple Polygon (2008)
Boris Aronov, Alan R. Davis, John Iacono, Albert Siu, Cheong Yu
Abstract. The complexity of the visibility region formed by a point light source after k diffuse reflections in a simple n-sided polygon is O(n 9), which is the first result polynomial in n, with no...
Discrete and computational geometry (2008)
Boris Aronov, Leonidas J. Guibas, Marek Teichmann, Li Zhang
In this paper we explore some novel aspects of visibility for stationary and moving points inside a simple polygon P. We provide a mechanism for expressing the visibility polygon from a point as the...
Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun, Micha Sharir
Abstract. Let B be a set of n unit balls in R 3. We show that the combinatorial complexity of the space of lines in R 3 that avoid all the balls of B is O(n 3+ε), for any ε>0. This result has...
Cutting circles into pseudo-segments and improved bounds for incidences (2008)
We show that n arbitrary circles in the plane can be cut into O(n 3/2+ε) arcs, for any ε> 0, such that any pair of arcs intersect at most once. This improves a recent result of Tamaki and...
Cell complexities in hyperplane arrangements (2008)
We derive improved bounds on the complexity of many cells in arrangements of hyperplanes in higher dimensions, and use these bounds to obtain a very simple proof of a bound, due to [2], on the sum of...
Complement Problem From Shallow to Shallower (2008)
R- set red points in IR 2. (i.e., loc. of soldiers of the spindle of infamy) B- set blue points in IR 2. (i.e., loc. of peace loving and freedom spreading soldiers). Q: Compute disk covering largest...
On the complexity of many faces in arrangements of pseudo-segments and of circles (2008)
Pankaj K. Agarwal, Boris Aronov, Micha Sharir
We obtain improved bounds on the complexity of m distinct faces in an arrangement of n pseudo-segments, n circles, or n unit circles. The bounds are worst-case optimal for unit circles; they are also...
Approximate Halfspace Range Counting ∗ (2008)
We present a simple scheme extending the shallow partitioning data structures of Matouˇsek, that supports efficient approximate halfspace range-counting queries in R d with relative error ε....
1997 Society for Industrial and Applied Mathematics (2007)
Boris Aronov, Micha Sharir, Boaz Tagansky, Pii S
Abstract. We show that the number of vertices, edges, and faces of the union of k convex polyhedra in 3-space, having a total of n faces, is O(k 3 + kn log k). This bound is almost tight in the worst...
Sariel Har-peled, Timothy M. Chan, Boris Aronov, Dan Halperin, Jack Snoeyink
This note considers the complexity of a free region in the configuration space of a polygonal robot translating amidst polygonal obstacles in the plane. Specifically, given polygonal sets P and Q...
Boris Aronov, Mark De Berg, Jules Vleugels
We study the motion-planning problem for pairs and triples of robots operating in a shared workspace containing n obstacles. A standard way to solve such problems is to view the collection of robots...
Abstract. It is known that a scene consisting of k convex polyhedra of total complexity n has at most O(n 4
We show that the number of distinct distances determined by any set of n points in three dimensions is at least
We derive improved bounds on the complexity of many cells in arrangements of hyperplanes in higher dimensions, and use these bounds to obtain a very simple proof of a bound, due to [2], on the sum of...
Cutting circles into pseudo-segments and improved bounds for incidences (2007)
We show that n arbitrary circles in the plane can be cut into O(n
Herve Bronnimann Yi-Jen Chiang (2007)
Abstract It is known that a scene consisting of k convex polyhedra of total complexity n has at most O((n 2
On the Number of Minimal 1-Steiner Trees (2007)
We count the number of nonisomorphic geometric minimum spanning trees formed by adding a single point to an n-point set in d-dimensional space, by relating it to a family of convex decompositions of...
Approximation Algorithms for Minimum-Width Annuli and Shells (2007)
Pankaj K. Agarwal, Boris Aronov, Sariel Har-peled, Micha Sharir
The \roundness" of S can be measured by computing the width ! (S) of the thinnest spherical shell (or annulus in ) that contains S. This paper contains two main results related to computing :...
Sparse geometric graphs with small dilation (2007)
Aronov, Boris, De Berg, Mark, Cheong, Otfried, Gudmundsson, Joachim, Haverkort, Herman, Smid, Michiel, ...
Given a set S of n points in R^D, and an integer k such that 0
On approximate halfspace range counting and relative epsilon-approximations (2007)
The paper consists of two major parts. In the first part, we re-examine relative ε-approximations, previously studied in [12, 13, 18, 25], and their relation to certain geometric problems, most...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, ...
We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line ℓ in the...
Fréchet distance for curves, revisited (2006)
Boris Aronov, Sariel Har-peled, Christian Knauer, Yusu Wang, Carola Wenk
Abstract. We revisit the problem of computing the Fréchet distance between polygonal curves, focusing on the discrete Fréchet distance, where only distance between vertices is considered. We...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, ...
We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line ℓ in the...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine
In the process of developing the second data structure, we develop a new representation of nearest-point and farthest-point Voronoi diagrams of points in convex position. This representation supports...
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, ...
Input: Let P ∈ � d be a set of points lying in convex position. Also given are a point p ∈ P and a halfspace ˆ h ∈ � d. Output: The point q ∈ P which is farthest from p in the halfspace,...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, ...
We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line ℓ in the...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, John Iacono, Stefan Langerman, Michiel Smid
Abstract. We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, ...
We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line ℓ in the...
Data structures for halfplane proximity queries and incremental Voronoi diagrams (2006)
Boris Aronov, Prosenjit Bose, Erik D. Demaine, John Iacono, Stefan Langerman, Michiel Smid
Abstract. We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line...
Polyline Fitting of Planar Points under Min-sum Criteria (2006)
Aronov, Boris, Asano, Tetsuo, Katoh, Naoki, Mehlhorn, Kurt, Tokuyama, Takeshi
Fitting a curve of a certain type to a given set of points in the plane is a basic problem in statistics and has numerous applications. We consider fitting a polyline with k joints under the min-sum...
Polyline fitting of planar points under min-sum criteria (2006)
ARONOV, BORIS, ASANO, TETSUO, KATOH, NAOKI, MEHLHORN, KURT, TOKUYAMA, TAKESHI
Fitting a curve of a certain type to a given set of points in the plane is a basic problem in statistics and has numerous applications. We consider fitting a polyline with k joints under the min-sum...
Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams (2005)
Aronov, Boris, Bose, Prosenjit, Demaine, Erik D., Gudmundsson, Joachim, Iacono, John, Langerman, Stefan, ...
We consider preprocessing a set S of n points in the plane that are in convex position into a data structure supporting queries of the following form: given a point q and a directed line l in the...
Computational Geometry 34 (2006) 159--181 (2005)
Www Elsevier Com, Boris Aronov, Hervé Brönnimann, Allen Y. Chang, Yi-jen Chiang
The ray shooting problem arises in many different contexts and is a bottleneck of ray tracing in computer graphics. Unfortunately, theoretical solutions to the problem are not very practical, while...
Sparse geometric graphs with small dilation (2005)
Boris Aronov, Mark Berg, Otfried Cheong, Joachim Gudmundsson, Herman Haverkort, Michiel Smid, ...
Given a set S of n points in R D, and an integer k such that 0 � k < n, we show that a geometric graph with vertex set S, at most n − 1 + k edges, maximum degree five, and dilation O(n/(k +...
Sparse geometric graphs with small dilation (2005)
Boris Aronov, Mark De Berg, Otfried Cheong, Joachim Gudmundsson, Herman Haverkort, Michiel Smid, ...
Abstract. Given a set S of n points in R D, and an integer k such that 0 � k < n, we show that a geometric graph with vertex set S, at most n − 1 + k edges, maximum degree five, and dilation...
On approximating the depth and related problems (2005)
Boris Aronov, Sariel Har-peled
We study the question of finding a deepest point in an arrangement of regions, and provide a fast algorithm for this problem using random sampling, showing it sufficient to solve this problem when...
On approximating the depth and related problems (2005)
Boris Aronov, Sariel Har-peled
We study the question of finding a deepest point in an arrangement of regions, and provide a fast algorithm for this problem using random sampling, showing it sufficient to solve this problem when...
A Generalization of Magic Squares with Applications to Digital Halftoning (2004)
Boris Aronov, Tetsuo Asano, Yosuke Kikuchi, Subhas C. N, Shinji Sasahara, Takeaki Uno
Abstract. A semimagic square of order n is an n¢n matrix containing the integers 0�����n2 1 arranged in such a way that each row and column add up to the same value. We generalize this...
On the union of κ-round objects in three and four dimensions (2004)
Boris Aronov, Alon Efrat, Vladlen Koltun, Micha Sharir
A compact set c in R d is κ-round if for every point p ∈ ∂c there exists a closed ball that contains p, is contained in c, and has radius κ diam c. We show that, for any fixed κ> 0, the...
Detecting duplicates among similar bit vectors (2004)
(of course, with geometric applications)
On the Union of ^-Round Objects in Three and Four Dimensions* (2004)
Boris Aronov, Alon Efrat, Vladlen Koltun, Micha Sharir
Abstract A compact body c in Rd is ^-round if for every point p 2 @c there exists a closed ball that contains p, is contained in c, and has radius ^ diam c. We show that, for any fixed ^> 0, the...
Www Elsevier Com, Boris Aronov, Hervé Brönnimann, Allen Y. Chang, Yi-jen Chiang
Given a scene consisting of objects, ray shooting queries answer with the first object encountered by a given ray, and are used in ray tracing and radiosity for rendering photo-realistic images in...
On the union of κ-round objects in three and four dimensions (2004)
Boris Aronov, Alon Efrat, Vladlen Koltun, Micha Sharir
A compact body c in R d is κ-round if for every point p ∈ ∂c there exists a closed ball that contains p, is contained in c, and has radius κ diam c. We show that, for any fixed κ> 0, the...
A Generalization of Magic Squares with Applications to Digital Halftoning (2004)
Boris Aronov, Tetsuo Asano, Yosuke Kikuchi, Subhas C. N, Shinji Sasahara, Takeaki Uno
Abstract. A semimagic square of order n is an n¢n matrix containing the integers 0�����n2 1 arranged in such a way that each row and column add up to the same value. We generalize this...
On lines avoiding unit balls in three dimensions (2004)
Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun, Micha Sharir
Let B be a set of n unit balls in R 3. We show that the combinatorial complexity of the space of lines in R 3 that avoid all the balls of B is O(n 3+ε), for any ε> 0. This result has connections...
Cutting triangular cycles of lines in space (2003)
Boris Aronov, Vladlen Koltun, Micha Sharir
We show that n lines in 3-space can be cut into O(n 2−1/69 log 16/69 n) pieces, such that all depth cycles defined by triples of lines are eliminated. This partially resolves a long-standing open...
Distinct Distances in Three and Higher Dimensions (2003)
Boris Aronov, Janos Pach, Micha Sharir, Gabor Tardos
Improving an old result of Clarkson et al., we show that the number of distinct distances determined by a set P of n points in three-dimensional space is 77=141 " ) = ), for any " > 0....
Distinct distances in three and higher dimensions (2003)
Boris Aronov, János Pach, Micha Sharir, Gábor Tardos
Improving an old result of Clarkson et al., we show that the number of distinct distances determined by a set P of n points in three-dimensional space is Ω(n 77/141−ε) = Ω(n 0.546), for any...
Distinct Distances in Three and Higher Dimensions (2003)
Boris Aronov, Janos Pach, Micha Sharir, Gabor Tardos
Improving an old result of Clarkson et al., we show that the number of distinct distances determined by a set P of n points in three-dimensional space is # n 77/141-# ) = ), for any # > 0....
Cutting triangular cycles of lines in space (2003)
Boris Aronov, Vladlen Koltun, Micha Sharir
We show that n lines in 3-space can be cut into O(n 2−1/69 log 16/69 n) pieces, such that all depth cycles defined by triples of lines are eliminated. This partially resolves a long-standing open...
Distinct distances in three and higher dimensions (2003)
Boris Aronov, János Pach, Micha Sharir, Gábor Tardos
Improving an old result of Clarkson et al., we show that the number of distinct distances determined by a set P of n points in three-dimensional space is Ω(n 77/141−ε) = Ω(n 0.546), for any...
Facility Location on Terrains (2002)
Aronov, Boris, Kreveld, Marc Van, Oostrum, René Van, Varadarajan, Kasturi
Cost prediction for ray shooting (2002)
Boris Aronov, Hervé Brönnimann, Allen Y. Chang, Yi-jen Chiang
The ray shooting problem arises in many different contexts. For example, solving it efficiently would remove a bottleneck when images are ray-traced in computer graphics. Unfortunately, theoretical...
Motion Planning for a Convex Polygon in a Polygonal Environment (2002)
Pankaj K. Agarwal, Boris Aronov, Micha Sharir
We study the motion-planning problem for a convex m-gon P in a planar polygonal environment Q bounded by n edges. We give the rst algorithm that constructs the entire free con guration space (the...
Incidences between points and circles in three and higher dimensions (2002)
Boris Aronov, Vladlen Koltun, Micha Sharir
We show that the number of incidences between m distinct points and n distinct circles in R d, for any d ≥ 3, is O(m 6/11 n 9/11 κ(m 3 /n)+m 2/3 n 2/3 +m+n), where κ(n) = (log n) O(α2 (n)) and...
Exact and Approximation Algorithms for Minimum-Width Cylindrical Shells (2001)
Pankaj K. Agarwal, Boris Aronov, Micha Sharir
Let S be a set of n points in R 3 . Let ! = ! (S) be the width (i.e., thickness) of a minimum-width infinite cylindrical shell (the region between two co-axial cylinders) containing S. We first...
On Levels in Arrangements of Lines, Segments, Planes, and Triangles (2001)
Pankaj K. Agarwal, Boris Aronov, Timothy M. Chan, Micha Sharir
We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and an extension of, the well-known k-set problem. Among other...
We derive improved upper bounds for the number of incidences between m points and n circles in the plane, and for the complexity of m distinct faces in an arrangement of circles. An improved...
A Helly-type theorem for higher-dimensional transversals (2000)
Boris Aronov, Boris Aronov, Jacob E. Goodman, Jacob E. Goodman, Richard Pollack, Richard Pollack
We generalize the Hadwiger(-Danzer-Grunbaum-Klee) theorem on line transversals for an unbounded family of compact convex sets to the case of transversal planes of arbitrary dimension.
Approximation and Exact Algorithms for Minimum-Width Annuli and Shells (1999)
Pankaj K. Agarwal, Boris Aronov, Sariel Har-peled, Micha Sharir
Let S be a set of n points in R d . The "roundness" of S can be measured by computing the width ! = ! (S) of the thinnest spherical shell (or annulus in R 2 ) that contains S. This paper...
Polytopes in Arrangements (1999)
Consider an arrangement of n hyperplanes in R d . Families of convex polytopes whose boundaries are contained in the union of the hyperplanes are the subject of this paper. We aim to bound their...
On Levels in Arrangements of Lines, Segments, Planes, and Triangles (1998)
Agarwal, Pankaj K., Aronov, Boris, Sharir, Micha
We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and extending the well-known k-set problem. (a) We review and...
On the Complexity of Many Faces in Arrangements of Circles (1998)
Agarwal, Pankaj K., Aronov, Boris, Sharir, Micha
We obtain improved bounds on the complexity of m distinct faces in an arrangement of n circles and in an arrangement of n unit circles. The bounds are worst-case tight for unit circles, and, for...
Polyline fitting of planar points under min-sum criteria (1998)
Boris Aronov, Tetsuo Asano, Naoki Katoh, Kurt Mehlhorn, Takeshi Tokuyama
Fitting a curve of a certain type to a given set of points in the plane is a basic problem in statistics and has numerous applications. We consider fitting a polyline with k joints under the min-sum...
Results on k-sets and j-facets via continuous motion (1998)
Artur Andrzejak, Boris Aronov, Sariel Har-peled, Raimund Seidel, Emo Welzl
Let P be a set of n points in IR
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...
On levels in arrangements of lines, segments, planes, and triangles (1998)
Pankaj K. Agarwal, Boris Aronov, Micha Sharir
We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and extending, the well-known k-set problem. (a) We review and...
On the Number of Regular Vertices of the Union of Jordan Regions (1998)
Boris Aronov, Alon Efrat, Dan Halperin, Micha Sharir
Let C be a collection of n Jordan regions in the plane in general position, such that each pair of their boundaries intersect in at most s points, where s is a constant. Let U denote the union of C....
Visibility Queries in Simple Polygons and Applications (1998)
Boris Aronov, Leonidas J. Guibas, Marek Teichmann, Li Zhang
. In this paper we explore some novel aspects of visibility for stationary and moving points inside a simple polygon P . We provide a mechanism for expressing the visibility polygon from a point as...
Polyline Fitting of Planar Points under Min-Sum (1998)
Criteria Boris Aronov, Boris Aronov, Tetsuo Asano, Naoki Katoh, Kurt Mehlhorn, Takeshi Tokuyama Polytechnic
Fitting a curve of a certain type to a given set of points in the plane is a basic problem in statistics and has numerous applications. We consider fitting a polyline with k joints under the min-sum...
On levels in arrangements of lines, segments, planes, and triangles. Discrete Comput. Geom (1998)
Pankaj K. Agarwal, Boris Aronov, Timothy M. Chan, Micha Sharir
Abstract We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and an extension of, the well-known k-set problem. Among...
Visibility queries in simple polygons and applications (1998)
Boris Aronov, Leonidas J. Guibas, Marek Teichmann, Li Zhang
Abstract. In this paper we explore some novel aspects of visibility for stationary and moving points inside a simple polygon §. We provide a mechanism for expressing the visibility polygon from a...
Quasi-planar graphs have a linear number of edges. (1997)
Agarwal, Pankaj K., Aronov, Boris, Pach, János, Pollack, Richard, Sharir, Micha
Computing envelopes in four dimensions with applications (1997)
Pankaj K. Agarwal, Boris Aronov, Micha Sharir
Abstract. Let F be a collection of nd-variate, possibly partially defined, functions, all algebraic of some constant maximum degree. We present a randomized algorithm that computes the vertices,...
On translational motion planning of a convex polyhedron in 3-space (1997)
Abstract. Let B be a convex polyhedron translating in 3-space amidst k convex polyhedral obstacles A 1,..., A k with pairwise disjoint interiors. The free configuration space (space of all...
Line Transversals of Balls and Smallest Enclosing Cylinders in Three Dimensions (1997)
Pankaj K. Agarwal, Pankaj K. Agarwal, Boris Aronov, Boris Aronov, Micha Sharir, Micha Sharir
We establish a near-cubic upper bound on the complexity of the space of line transversals of a collection of n balls in three dimensions, and show that the bound is almost tight, in the worst case....
Visibility with One Reflection (1997)
Boris Aronov, Alan R. Davis, Tamal K. Dey, Sudebkumar P. Pal, D. Chithra Prasad
We extend the concept of the polygon visible from a source point S in a simple polygon by considering visibility with two types of reflection, specular and diffuse. In specular reflection a light ray...
On Levels in Arrangements of Lines, Segments, Planes, and Triangles (1997)
Pankaj K. Agarwal, Boris Aronov, Timothy M. Chan, Micha Sharir
We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and an extension of, the well-known k-set problem. Among other...
The Common Exterior of Convex Polygons in the Plane (1997)
We establish several combinatorial bounds on the complexity (number of vertices and edges) of the complement of the union (also known as the common exterior) of k convex polygons in the plane, with a...
Computing Envelopes in Four Dimensions with Applications (1997)
Pankaj K. Agarwal, Pankaj K. Agarwal, Boris Aronov, Boris Aronov, Micha Sharir, Micha Sharir
Let F be a collection of n d-variate, possibly partially defined, functions, all algebraic of some constant maximum degree. We present a randomized algorithm that computes the vertices, edges, and...
Motion Planning for a Convex Polygon in a Polygonal Environment (1997)
Pankaj K. Agarwal, Boris Aronov, Micha Sharir
We study the motion-planning problem for a convex m-gon P in a planar polygonal environment Q bounded by n edges. We give the first algorithm that constructs the entire free configuration space (the...
Line Transversals of Balls and Smallest Enclosing Cylinders in Three Dimensions (1997)
Pankaj K. Agarwal, Boris Aronov, Micha Sharir
We establish a near-cubic upper bound on the complexity of the space of line transversals of a collection of n balls in three dimensions, and show that the bound is almost tight, in the worst case....
Results on k-Sets and j-Facets via Continuous Motion (1997)
Artur Andrzejak, Boris Aronov, Sariel Har-peled, Raimund Seidel, Emo Welzl
Let P be a set of n points in IR d in general position, i.e., no i + 1 points on a common (i \Gamma 1)-flat, 1 i d. A k-set of P is a set S of k points in P that can be separated from P nS by a...
Star unfolding of a polytope with applications (1997)
Pankaj K. Agarwal, Boris Aronov, Catherine A. Schevon
Abstract. We introduce the notion of a star unfolding of the surface P of a three-dimensional convex polytope with n vertices, and use it to solve several problems related to shortest paths on P. The...
Quasi-Planar Graphs Have a Linear Number of Edges (1996)
Agarwal, Pankaj K., Aronov, Boris, Pach, János, Pollack, Richard, Sharir, Micha
A graph is called quasi-planar if it can be drawn in the plane so that no three of its edges are pairwise crossing. It is shown that the maximum number of edges of a quasi-planar graph with n...
Quasi-Planar Graphs Have a Linear Number of Edges (1996)
Agarwal, Pankaj K., Aronov, Boris, Pach, János, Pollack, Richard, Sharir, Micha
A graph is called quasi-planar if it can be drawn in the plane so that no three of its edges are pairwise crossing. It is shown that the maximum number of edges of a quasi-planar graph with n...
Quasi-Planar Graphs Have a Linear Number of Edges (1996)
Agarwal, Pankaj K., Aronov, Boris, Pach, János, Pollack, Richard, Sharir, Micha
A graph is called quasi-planar if it can be drawn in the plane so that no three of its edges are pairwise crossing. It is shown that the maximum number of edges of a quasi-planar graph with n...
Visibility with Multiple Reflections (1996)
Boris Aronov, Alan R. Davis, Tamal K. Dey, Sudebkumar P. Pal, D. Chithra Prasad
We show that the region lit by a point light source inside a simple n-gon after at most k reflections off the boundary has combinatorial complexity O(n 2k ), for any k 1. A lower bound of...
On Levels in Arrangements of Lines, Segments, Planes, and Triangles (1996)
Pankaj K. Agarwal, Boris Aronov, Micha Sharir
We consider the problem of bounding the complexity of the k-th level in an arrangement of n curves or surfaces, a problem dual to, and extending, the well-known k-set problem. (a) We review and...
Largest Placements and Motion Planning of a Convex Polygon (1996)
Pankaj K. Agarwal, Nina Amenta, Boris Aronov, Micha Sharir
We study two problems involving collision-free placements of a convex m-gon P in a planar polygonal environment: (i) We first show that the largest similar copy of P inside another convex polygon Q...
Boris Aronov Anos, Pankaj K. Agarwal, Boris Aronov, Richard Pollack, Micha Sharir
A graph is called quasi-planar if it can be drawn in the plane so that no three of its edges are pairwise crossing. It is shown that the maximum number of edges of a quasi-planar graph with n...
The Complexity of a Single Face of a Minkowski Sum (1995)
Sariel Har-peled, Timothy M. Chan, Boris Aronov, Dan Halperin, Jack Snoeyink
This note considers the complexity of a free region in the configuration space of a polygonal robot translating amidst polygonal obstacles in the plane. Specifically, given polygonal sets P and Q...
Quasi-Planar Graphs Have a Linear Number of Edges (1995)
Pankaj Agarwal, Boris Aronov, Richard Pollack, Micha Sharir
A graph is called quasi-planar if it can be drawn in the plane so that no three of its edges are pairwise crossing. It is shown that the maximum number of edges of a quasi-planar graph with n...
Online Maintenance of Visibility and Shortest-Path Information (1994)
Given a simple polygon P and a point p 2 P , we show how to maintain the visibility polygon from p, the shortest path tree from p, and the corresponding shortest path partition as p is translated...
Boris Aronov, Paul Erdős, Wayne Goddard, Daniel J. Kleitman, Michael Klugerman, János Pach, ...
Given a set of points in the plane, a crossing family is a collection of line segments, each joining two of the points, such that any two line segments intersect internally. Two sets A and B of...
On the zone of a surface in a hyperplane arrangement (1993)
Boris Aronov, Marco Pellegrini, Micha Sharir
Let H be a collection of n hyperplanes in IR d, let A denote the arrangement of H; and let oe be a (d \Gamma 1)-dimensional algebraic surface of low degree, or the boundary of a convex set in IR d....
Star Unfolding of a Polytope with Applications (1993)
Pankaj K. Agarwal, Pankaj K. Agarwal, Joseph O'Rourke, Boris Aronov, Boris Aronov, Catherine A. Schevon, ...
We define the notion of a star unfolding of the surface P of a convex polytope with n vertices, and use it to solve several problems related to shortest paths on P. The first algorithm computes the...
Can Visibility Graphs Be Represented Compactly? (1993)
Pankaj K. Agarwal, Pankaj K. Agarwal, Noga Alon, Noga Alon, Boris Aronov, Boris Aronov, ...
We consider the problem of representing the visibility graph of line segments as a union of cliques and bipartite cliques. Given a graph G, a family G = fG 1 ; G 2 ; : : : ; G k g is called a clique...
On Compatible Triangulations of Simple Polygons (1993)
Boris Aronov, Raimund Seidel, Diane Souvaine
It is well known that, given two simple n-sided polygons, it may not be possible to triangulate the two polygons in a compatible fashion, if one's choice of triangulation vertices is restricted...
Line Stabbing Bounds in Three Dimensions (1993)
Pankaj K. Agarwal, Boris Aronov, Subhash Suri
Let S be a set of (possibly degenerate) triangles in ! 3 whose interiors are disjoint. A triangulation of ! 3 with respect to S, denoted by T (S), is a simplicial complex in which the interior of no...
An invariant property of balls in arrangements of hyperplanes. (1993)
Aronov, Boris, Naiman, Daniel Q., Pach, János, Sharir, Micha
Combinatorial and algorithmic analysis of space decomposition problems / (1989)
Thesis (Ph. D.)--New York University, 1989.
On the Helly Number for Hyperplane Transversals to Unit Balls
Boris Aronov, Jacob E. Goodman, Richard Pollack, Rephael Wenger
We prove some results about the Hadwiger problem of finding the Helly number for line transversals of disjoint unit disks in the plane, and about its higher-dimensional generalization to hyperplane...