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
Counting Triangulations of Planar Point Sets (2009)
Sharir, Micha, Sheffer, Adam, Welzl, Emo
We study the maximal number of triangulations that a planar set of $n$ points can have, and show that it is at most $30^n$. This new bound is achieved by a careful optimization of the charging scheme...
Linear Data Structures for Fast Ray-Shooting amidst Convex (2009)
Haim Kaplan, Natan Rubin, Micha Sharir
We consider the problem of ray shooting in a three-dimensional scene consisting of k (possibly intersecting) convex polyhedra with a total of n facets. That is, we want to preprocess them into a data...
The Complexity of the Outer Face in Arrangements of Random Segments ∗ (2009)
Noga Alon, Dan Halperin, Oren Nechushtan, Micha Sharir
We investigate the complexity of the outer face in arrangements of line segments of a fixed length ℓ in the plane, drawn uniformly at random within a square. We derive upper bounds on the expected...
Adrian Dumitrescu, Micha Sharir, Csaba D. Tóth
problems on triangle areas in two and three dimensions ∗
Haim Kaplan, Edgar Ramos, Micha Sharir
In approximate halfspace range counting, one is given a set P of n points in R d, and an ε> 0, and the goal is to preprocess P into a data structure which can answer efficiently queries of the...
Relative $(p,\epsilon)$-Approximations in Geometry (2009)
Har-Peled, Sariel, Sharir, Micha
We re-examine the notion of relative $(p,\eps)$-approximations, recently introduced in [CKMS06], and establish upper bounds on their size, in general range spaces of finite VC-dimension, using the...
Semi-algebraic Range Reporting and Emptiness Searching with Applications (2009)
In a typical range emptiness searching (resp., reporting) problem, we are given a set $P$ of $n$ points in $\reals^d$, and wish to preprocess it into a data structure that supports efficient range...
Kaplan, Haim, Sharir, Micha, Shustin, Eugenii
Let $L$ be a set of $n$ lines in $\reals^d$, for $d\ge 3$. A {\em joint} of $L$ is a point incident to at least $d$ lines of $L$, not all in a common hyperplane. Using a very simple algebraic proof...
On Lines, Joints, and Incidences in Three Dimensions (2009)
Elekes, György, Kaplan, Haim, Sharir, Micha
We extend (and somewhat simplify) the algebraic proof technique of Guth and Katz \cite{GK}, to obtain several sharp bounds on the number of incidences between lines and points in three dimensions....
COMPUTINGAFACE INANARRANGEMENTOFLINESEGMENTSAND RELATEDPROBLEMS* (2009)
Bernard Chazellet, Herbert Edelsbrunnert, Leonidas Guibas, Micha Sharir, Jack Snoeyink
Abstract. Thispaperpresents arandomizedincremental algorithm forcomputing a single face inanarrangement of n line segments in the plane that is fairly simple to implement. The expected running time...
Constructing Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes in Space ∗ (2008)
Dan Halperin, Ophir Setter, Micha Sharir
We present a general framework for computing two-dimensional Voronoi diagrams of different site classes under various distance functions. The computation of the diagrams employs the Cgal software for...
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
Contemporary Mathematics State of the Union (of Geometric Objects) (2008)
Pankaj K. Agarwal, János Pach, Micha Sharir
ABSTRACT. Let C be a set of geometric objects in R d. The combinatorial complexity of the union of C is the total number of faces of all dimensions on its boundary. We survey the known upper bounds...
Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir
A singly exponential stratification scheme for real semi-algebraic varieties and its applications*
Combinatorial Geometry with Algorithmic Applications – The Alcala Lectures (2008)
These lecture notes are a compilation of surveys of the topics that are presented
Line Transversals of Convex Polyhedra in $\reals^3$ (2008)
Kaplan, Haim, Rubin, Natan, Sharir, Micha
We establish a bound of $O(n^2k^{1+\eps})$, for any $\eps>0$, on the combinatorial complexity of the set $\T$ of line transversals of a collection $\P$ of $k$ convex polyhedra in $\reals^3$ with a...
Eppstein's bound on intersecting triangles revisited (2008)
Nivasch, Gabriel, Sharir, Micha
Let S be a set of n points in the plane, and let T be a set of m triangles with vertices in S. Then there exists a point in the plane contained in Omega(m^3 / (n^6 log^2 n)) triangles of T. Eppstein...
SELECTINGHEAVILYCOVEREDPOINTS* (2008)
Herbert Edelsbrunnert, Leonidas J. Guibas, John E, Hershberger Raimund, Seidel Ii, Micha Sharir
Abstract. A collection ofgeometric selection lemmas is proved, such as the following: Forany set P ofn points in three-dimensional space and any set,9 ofm spheres, where each sphere passes through a...
Abstract The 2-Center Problem with Obstacles* (2008)
Dan Halperin, Micha Sharir, Ken Goldberg
Given a set S of n points in the plane and a set O of pairwise disjoint simple polygons with a total of m edges, we wish to find two congruent disks of small-est radius whose union covers S and whose...
Curve-sensitive cuttings (2008)
We introduce (1/r)-cuttings for collections of surfaces in 3-space that are sensitive to an additional collection of curves. Specifically, let S be a set of n surfaces in R 3 of constant description...
The partition technique for overlays of envelopes (2008)
We obtain a near-tight bound of O(n 3+ε), for any ε> 0, on the complexity of the overlay of the minimization diagrams of two collections of surfaces in four dimensions. This settles a...
Abstract Online Conflict-Free Coloring for Intervals (2008)
Amos Fiat, Meital Levy, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
Algorithms for Weak "-Nets (2008)
Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, Emo Welzl
In the plane, we can nd a weak "-net for convex sets consisting of O( ",2) points, in time O(n ",2). We can determine the smallest " for which a given planar set...
Haim Kaplan, Natan Rubin, Micha Sharir
Abstract. We consider the problem of ray shooting in a three-dimensional scene consisting of k (possibly intersecting) convex polyhedra with a total of n facets. That is, we want to preprocess them...
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...
The Simplex Algorithm in Dimension Three 1 (2008)
Volker Kaibel, Rafael Mechtel, Micha Sharir, Günter M. Ziegler
We investigate the worst-case behavior of the simplex algorithm on linear programs with 3 variables, that is, on 3-dimensional simple polytopes. Among the pivot rules that we consider, the “random...
On the number of directions determined by a three-dimensional points set (2008)
János Pach, Rom Pinchasi, Micha Sharir
Let P be a set of n points in R 3, not all of which are in a plane and no three on a line. We partially answer a question of Scott (1970) by showing that the connecting lines of P assume at least 2n...
On empty convex polygons in a planar point set (2008)
Let P be a set of n points in general position in the plane. Let Xk(P) denote the number of empty convex k-gons determined by P. We derive, using elementary proof techniques, several equalities and...
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...
Repeated angles in three and four dimensions (2008)
Abstract. We show that the maximum number of occurrences of a given angle in a set of n points in � 3 is O(n 7/3), and that a right angle can actually occur Ω(n 7/3) times. We then show that the...
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...
Abstract Counting Colors in Boxes ∗ (2008)
Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin
Let P be a set of n points in R d, so that each point is colored by one of C given colors. We present algorithms for preprocessing P into a data structure that efficiently supports queries of the...
Arrangements in Geometry: Recent Advances and Challenges ⋆ (2008)
Abstract. We review recent progress in the study of arrangements in computational and combinatorial geometry, and discuss several open problems and areas for further research. In this talk I will...
Sergey Bereg, Micha Sharir, Ovidiu Daescu, Simeon Ntafos, Binhai Zhu
Given a polyhedral terrain § with ¨ vertices, the two-watchtower problem for § asks to find two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases) lie...
Bi-criteria Linear-time Approximations for Generalized k-Mean/Median/Center ABSTRACT (2008)
We consider the problem of approximating a set P of n points in R d by a collection of j-dimensional flats, and extensions thereof, under the standard median / mean / center measures, in which we...
3-DIMENSIONAL EUCLIDEAN VORONOI DIAGRAMS OF LINES WITH A FIXED NUMBER OF ORIENTATIONS ∗ (2008)
Abstract. We show that the combinatorial complexity of the Euclidean Voronoi diagram of n lines in R 3 that have at most c distinct orientations is O(c 3 n 2+ε) for any ε>0. This result is a...
Curve-sensitive cuttings (2008)
We introduce (1/r)-cuttings for collections of surfaces in 3-space, such that the cuttings are sensitive to an additional collection of curves. Specifically, let S be a set of n surfaces and let C be...
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...
The partition technique for overlays of envelopes (2008)
Abstract We obtain a near-tight bound of O(n3+"), for any "> 0, on the complexity of theoverlay of the minimization diagrams of two collections of surfaces in four dimensions....
A single cell in an arrangement of convex polyhedra (2008)
Abstract We show that the combinatorial complexity of a single cell in an arrangement of kconvex polyhedra in 3-space having n facets in total is O(nk1+"), for any "> 0,...
1 1 Motion Planning in the Presence of Moving Obstacles (2008)
This paper investigates the computational complexity of planning the mo-tion of a body B in 2{D or 3{D space, so as to avoid collision with moving ob-stacles of known, easily computed, trajectories....
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...
Computing the detour and spanning ratio of paths, trees and cycles in 2D and 3D (2008)
Pankaj K. Agarwal, Rolf Klein, Christian Knauer, Stefan Langerman, Pat Morin, Micha Sharir, ...
The detour and spanning ratio of a graph � embedded in �� � measure how well � approximates Euclidean space and the complete Euclidean graph, respectively. In this paper we describe...
Approximation and Exact Algorithms for Minimum-Width Annuli and Shells\Lambda (2008)
Pankaj K. Agarwaly, Boris Aronovz, Sariel Har-peledx, Micha Sharir
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...
Efficient Generation of k-Directional Assembly Sequences (2008)
Pankaj K. Agarwal, Mark De Berg, Dan Halperin, Micha Sharir
Let S be a collection of n rigid bodies in 3-space, and let D be a set of k directions in 3-space, where k is a small constant. A k-directional assembly sequence for S, with respect to D, is a linear...
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 ε....
Line Transversals of Convex Polyhedra in R 3∗ (2008)
Haim Kaplan, Natan Rubin, Micha Sharir
We establish a bound of O(n 2 k 1+ε), for any ε> 0, on the combinatorial complexity of the set T of line transversals of a collection P of k convex polyhedra in R 3 with a total of n facets, and...
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...
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...
Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, Emo Welzl
In the plane, we can find a weak "-net for convex sets consisting of O(" \Gamma2 points, in time O(n" \Gamma2). We can determine the smallest " for which a given...
Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, Emo Welzl
Let S be a set of n points in IR d. A set W is a weak "-net for (convex ranges of) S if for any T ` S containing "n points, the convex hull of T intersects W. We show the existence...
1 1 Motion Planning in the Presence of Moving Obstacles (2007)
This paper investigates the computational complexity of planning the motion of a body B in 2--D or 3--D space, so as to avoid collision with moving obstacles of known, easily computed, trajectories....
Efficient Generation of (2007)
Proc Th, Pankaj K. Agarwal, Mark De Berg, Dan Halperin, Micha Sharir
Let S be a collection of n rigid bodies in 3-space, and let D be a set of k directions in 3-space, where k is a small constant. A k-directional assembly sequence for S, with respect to D, is a linear...
Efficient Generation of (2007)
To Appear, Pankaj K. Agarwal, Mark De Berg, Dan Halperin, Micha Sharir
Let S be a collection of n rigid bodies in 3-space, and let D be a set of k directions in 3-space, where k is a small constant. A k-directional assembly sequence for S, with respect to D, is a linear...
The Random Edge Rule on Three-Dimensional Linear Programs 1 (2007)
Volker Kaibel, Rafael Mechtel, Micha Sharir, Gunter M. Ziegler
The worst-case expected length of the path taken by the simplex algorithm with the Random Edge pivot rule on a 3-dimensional linear program with n constraints is shown to be bounded by
Shakhar Smorodinsky, Micha Sharir
In this paper we prove several point-selection theorems concerning objects \spanned " by a nite set of points. For example, we show that for any set P of n points in IR 2 and any set C of m...
Extremal Congurations and Levels in Pseudoline Arrangements (2007)
Micha Sharir, Shakhar Smorodinsky
This paper studies a variety of problems involving certain types of extreme congurations in arrangements of (x-monotone) pseudo-lines. For example, we obtain a very simple proof of the bound O(nk
to appear in Combinatorics Probability and Computing. Point-Line Incidences in Space (2007)
Given a set L of n lines in R
The Random Edge Rule on Three-Dimensional Linear Programs 1 (2007)
Volker Kaibel, Rafael Mechtel, Micha Sharir, Gunter M. Ziegler
The worst-case expected length of the path taken by the simplex algorithm with the Random Edge pivot rule on a 3-dimensional linear program with n constraints is shown to be bounded by
Micha Sharir, Shakhar Smorodinsky
We introduce a new notion of `neighbors ' in geometric permutations. We conjecture that the maximum number of neighbors in a set of n pairwise disjoint convex bodies in R
On Polytopes Spanned by Sets of Points in IR 3 (2007)
Micha Sharir, Shakhar Smorodinsky
(a) We prove that the total complexity of k polygons in arrangement of n lines with distinct vertices is (nk 1=2). If the polygons do not overlap in edges then we show that their complexity is (nk
Shakhar Smorodinsky, Micha Sharir
In this paper we prove several point-selection theorems concerning objects \spanned " by a nite set of points. In the planar case we show the following: (i) For any set P of n points in IR
Reaching a Goal with Directional Uncertainty (2007)
Mark Berg, Mark Berg, Mark Overmars, Mark Overmars, Micha Sharir, Micha Sharir, ...
Overmars 1
Van Kreveld, Micha Sharir, Jack Snoeyink, Peter Rousseeuw, Bettina Speckmann
We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual...
A recent result by Pach and Pinchasi on so-called balanced lines of a nite two-colored point set in the plane is related to other facts on halving triangles in 3-space and to a special case of the...
We show that the number of distinct distances determined by any set of n points in three dimensions is at least
The union of congruent cubes in three dimensions (2007)
A dihedral (trihedral) wedge is the intersection of two (resp. three) half-spaces in R 3. It is called -fat if the angle (resp., solid angle) determined by these half-spaces is at least > 0. If,...
Pankaj K. Agarwal, Mark De Berg, Sariel Har-peled, Mark H. Overmars, Micha Sharir
Abstract. Let P = fP1; : : : ; Pmg be a set of m convex polytopes in R
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...
Pankaj K. Agarwal, Micha Sharir
We derive improved bounds on the number of triangles or tetrahedra spanned by a set of n points in R d that are congruent to a given triangle or tetrahedron. More generally, let
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
Radial Points in the Plane (2007)
A radial point for a finite set P in the plane is a point q 62 P with the property that each line connecting q to a point of P passes through at least one other element of P. We prove a conjecture of...
Shakhar Smorodinsky, Micha Sharir
We prove that the maximum number of geometric permutations, induced by line transversals to a collection of n pairwise disjoint balls in IR d, is \Theta(n d\Gamma1
Depth in Arrangements (Draft) (2007)
The depth of a point with respect to an arrangement of hyperplanes is dened as the minimum number of hyperplanes crossed by a ray from the point. The depth of an arrangement of hyperplanes is then de...
Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions ⋆ (2007)
Pankaj K. Agarwal, Mark De Berg, Sariel Har-peled, Mark H. Overmars, Micha Sharir, Jan Vahrenhold
Abstract. Let P = {P1,..., Pm} be a set of m convex polytopes in R d, for d = 2, 3, with a total of n vertices. We present output-sensitive algorithms for reporting all k pairs of indices (i, j) such...
Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions (2007)
Pankaj K. Agarwal, Mark De Berg, Sariel Har-peled, Mark H. Overmars, Micha Sharir, Jan Vahrenhold
Let P = fP 1 ; : : : ; Pm g be a set of m convex polytopes in R d , for d = 2; 3, with a total of n vertices. We present output-sensitive algorithms for reporting all k pairs of indices (i; j) such...
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 :...
Abstract. The paper presents two algorithms involving shooting in three dimensions. We rst present a new algorithm for performing ray shooting amid several special classes of n triangles in three...
MINERVA Center for Geometry at Tel Aviv University. (2007)
Gady Kozma, Zvi Lotker, Micha Sharir
Some of the first routing algorithms for geographically aware wireless networks used the Delaunay triangulation among the network’s nodes as the underlying connectivity graph [4]. These solutions...
Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions (2007)
Pankaj K. Agarwal, Mark De Berg, Sariel Har-peled, Mark H. Overmars, Micha Sharir, Jan Vahrenhold
d , for d = 2; 3, with a total of n vertices. We present output-sensitive algorithms for reporting all k pairs of indices (i; j) such that P i intersects P j . For the planar case we describe a...
Extremal problems on triangle areas in two and three dimensions (2007)
Dumitrescu, Adrian, Sharir, Micha, Toth, Csaba D.
The study of extremal problems on triangle areas was initiated in a series of papers by Erd\H{o}s and Purdy in the early 1970s. In this paper we present new results on such problems, concerning the...
Solution of Scott's problem on the number of directions determined by a point set in 3-space. (2007)
Relative ε-Approximations in Geometry ∗ (2007)
Sariel Har-peled, Micha Sharir
We re-examine relative ε-approximations, previously studied in [Pol86, Hau92, LLS01, CKMS06], and their relation to certain geometric problems. We give a simple constructive proof of their existence...
Weak ɛ-nets and interval chains (2007)
Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky
We construct weak ɛ-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1 r-nets of size O(rα(r)), where α(r)...
State of the Union (of Geometric Objects): A Review ∗ (2007)
Pankaj K. Agarwal, János Pach, Micha Sharir
Let C be a set of geometric objects in R d. The combinatorial complexity of the union U(C) of C is the total number of faces of all dimensions, of the arrangement of the boundaries of the objects,...
Counting colors in boxes (2007)
Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin
Let P be a set of n points in R d, so that each point is colored by one of C given colors. We present algorithms for preprocessing P into a data structure that efficiently supports queries of the...
Almost tight bound for the union of fat tetrahedra in three dimensions (2007)
We show that the combinatorial complexity of the union of n “fat ” tetrahedra in 3-space (i.e., tetrahedra all of whose solid angles are at least some fixed constant) of arbitrary sizes, is O(n...
Computing the volume of the union of cubes (2007)
Pankaj K. Agarwal, Haim Kaplan, Micha Sharir
Let C be a set of n axis-aligned cubes in R 3, and let U(C) denote the union of C. We present an algorithm that can compute the volume of U(C) in time O(n 4/3 log n). The previously best known...
Counting colors in boxes (2007)
Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin
Let P be a set of n points in R d, so that each point is colored by one of C given colors. We present algorithms for preprocessing P into a data structure that efficiently supports queries of the...
Kinetic and Dynamic Data Structures for Closest Pairs and All Nearest Neighbors ∗ (2007)
Pankaj K. Agarwal, Haim Kaplan, Micha Sharir
We present simple fully dynamic and kinetic data structures, which are variants of a dynamic 2-dimensional range tree, for maintaining the closest pair and all nearest neighbors for a set of n moving...
Similar Simplices in a d-Dimensional Point Set ∗ (2007)
Pankaj K. Agarwal, Roel Apfelbaum, George Purdy, Micha Sharir
We consider the problem of bounding the maximum possible number fk,d(n) of ksimplices that are spanned by a set of n points in R d and are similar to a given simplex. We first show that f2,3(n) = O(n...
Kinetic and Dynamic Data Structures for Closest Pairs and All Nearest Neighbors ∗ (2007)
Pankaj K. Agarwal, Haim Kaplan, Micha Sharir
We present simple fully dynamic and kinetic data structures, which are variants of a dynamic 2-dimensional range tree, for maintaining the closest pair and all nearest neighbors for a set of n moving...
the University of British Columbia. (2007)
Marc Kreveld, Peter Rousseeuw, Micha Sharir, Jack Snoeyink, Bettina Speckmann, ...
M. Sharir supported by NSF Grants CCR-97-32101 and CCR-94-24398, by grants from the
Weak ɛ-nets and interval chains (2007)
Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky
We construct weak ɛ-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1 r-nets of size O(rα(r)), where α(r)...
Online conflict-free coloring for intervals. (2006)
Fiat, Amos, Matoušek, Jiří, Mossel, Elchanan, Pach, János, Sharir, Micha, Smorodinsky, Shakhar, ...
Yevgeny Schreiber, Micha Sharir
We present an optimal-time algorithm for computing (an implicit representation of) the shortest-path map from a fixed source s on the surface of a convex polytope P in three dimensions. Our algorithm...
Elad Verbin, Curriculum Vitæ, Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin, ...
received best paper award in Combinatorial Pattern Matching (CPM) 2006. To be published in Theoretical Computer Science, special issue on The Burrows-Wheeler Transform and its Applications (expected...
Abstract We present new algorithms for approximate range counting,where, for a specified "> 0, we want to count the number of data points in a query range, up to relative error...
On the number of crossing-free matchings, (cycles, and partitions (2006)
Abstract We show that a set of n points in the plane has at mostO(10.05n) perfect matchings with crossing-free straight-line
We present new algorithms for approximate range counting, where, for a specified ε> 0, we want to count the number of data points in a query range, up to relative error of ε. We first describe a...
Online Conflict-Free Coloring for Intervals 1 (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
Online Conflict-Free Coloring for Intervals 1 (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
Random triangulations of planar point sets (2006)
Let S be a finite set of n + 3 points in general position in the plane, with 3 extreme points and n interior points. We consider triangulations drawn uniformly at random from the set of all...
On overlays and minimization diagrams (2006)
The overlay of 2 ≤ m ≤ d minimization diagrams of n surfaces in R d is isomorphic to a substructure of a suitably constructed minimization diagram of mn surfaces in R d+m−1. This elementary...
Online conflict-free coloring for intervals (2006)
Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Ji Rí, Matou Sek, ...
Abstract. We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the...
Relative ε-Approximations in Geometry ∗ (2006)
Sariel Har-peled, Micha Sharir
We re-examine relative ε-approximations, previously studied in [Pol86, Hau92, LLS01], [CKMS06], and their relation to certain geometric problems. We give a simple constructive proof of their...
Crossing patterns of semi-algebraic sets. (2005)
Alon, Noga, Pach, János, Pinchasi, Rom, Radoicic, Rados, Sharir, Micha
Crossing patterns of semi-algebraic sets (2005)
Noga Alon, János Pach, Rom Pinchasi, Micha Sharir
We prove that, for every family F of n semi-algebraic sets in R d of constant description complexity, there exist a positive constant ε that depends on the maximum complexity of the elements of F,...
On Incidences Between Points and Hyperplanes ∗ (2005)
We show that if the number I of incidences between m points and n planes in R3 is sufficiently large, then the incidence graph (that connects points to their incident planes) contains a large...
Guarding a terrain by two watchtowers (2005)
Pankaj K. Agarwal, Sergey Bereg, Ovidiu Daescu, Simeon Ntafos, Micha Sharir, Binhai Zhu
Given a polyhedral terrain T with n vertices, the two-watchtower problem for T asks to find two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases) lie on...
Guarding a terrain by two watchtowers (2005)
Pankaj K. Agarwal, Sergey Bereg, Ovidiu Daescu, Haim Kaplan, Simeon Ntafos, Micha Sharir, ...
Given a polyhedral terrain T with n vertices, the two-watchtower problem for T asks to find two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases) lie on...
Lenses in arrangements of pseudo-circles and their applications (2004)
Pankaj K. Agarwal, Micha Sharir, Eran Nevo, Shakhar Smorodinsky
Abstract. A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of...
Online Conflict-Free Coloring for Intervals 1 (2004)
Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, Micha Sharir, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
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...
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...
Lenses in arrangements of pseudo-circles and their applications (2004)
Pankaj K. Agarwal, Eran Nevo, Janos Pach, Rom Pinchasi, Micha Sharir, Shakhar Smorodinsky
A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct...
k-sets in four dimensions (2004)
Micha Sharir, Shakhar Smorodinsky, Uli Wagner
We show, with an elementary proof, that the number of halving sim-plices in a set of n points in R 4 in general position is O(n 4−2/45). This improves the previous bound of O(n4−1/134). Our main...
Online Conflict-Free Coloring for Intervals 1 (2004)
Amos Fiat, Haim Kaplan, Meital Levy, Elchanan Mossel, János Pach, Micha Sharir, ...
We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has...
Output-sensitive construction of the union of triangles (2004)
Abstract. We present an efficient algorithm for the following problem: Given a collection T = {Δ1,...,Δn} of n triangles in the plane, such that there exists a subset S ⊂ T (unknown to us) of ξ...
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...
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...
The Simplex Algorithm in Dimension Three (2003)
Kaibel, Volker, Mechtel, Rafael, Sharir, Micha, Ziegler, Guenter M.
We investigate the worst-case behavior of the simplex algorithm on linear programs with three variables, that is, on 3-dimensional simple polytopes. Among the pivot rules that we consider, the...
The Random Edge Rule on Three-Dimensional Linear Programs (2003)
Kaibel, Volker, Mechtel, Raphael, Sharir, Micha, Ziegler, Günter M.
The worst-case expected length f(n) of the path taken by the simplex algorithm with the Random Edge pivot rule on a 3-dimensional linear program with n constraints is shown to be bounded by 1.3445 n
Hausdorff distance under translation for points, disks, and balls (2003)
Pankaj K. Agarwal, Sariel Har-peled, Micha Sharir, Yusu Wang
We study the shape matching problem under the Hausdorff distance and its variants. In the first part of the paper, we consider two sets A, B of balls in R d, d = 2, 3, and wish to find a translation...
The Clarkson-Shor technique revisited and extended (2003)
We provide an alternative, simpler and more general derivation of the Clarkson-Shor probabilistic technique [6] and use it to obtain in addition several extensions and new combinatorial bounds. 1
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...
An improved bound for joints in arrangements of lines in space (2003)
Let L be a set of n lines in space. A joint of L is a point in R 3 where at least three non-coplanar lines meet. We show that the number of joints of L is O(n
Balanced Lines, Halving Triangles, and the Generalized Lower Bound Theorem (2003)
A recent result by Pach and Pinchasi on so-called balanced lines of a finite two-colored point set in the plane is related to other facts on halving triangles in 3-space and to a special case of the...
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...
Hausdorff distance under translation for points, disks, and balls (2003)
Pankaj K. Agarwal, Sariel Har-peled, Micha Sharir, Yusu Wang
We study the shape matching problem under the Hausdorff distance and its variants. In the first part of the paper, we consider two sets A, B of balls in R d, d = 2, 3, and wish to find a translation...
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...
Translating a Planar Object to Maximize Point Containment (2002)
Agarwal,Pankaj, Hagerup,Torben, Ray,Rahul, Sharir,Micha, Smid,Michiel, Welzl,Emo
Let $C$ be a compact set in $\IR^2$ and let $S$ be a set of $n$ points in $\IR^2$. We consider the problem of computing a translate of $C$ that contains the maximum number, $\kappa^*$, of points...
Implementation and Experimentation with Motion Planning Algorithms (2002)
The main charter of this contract is the implementation and experimentation with motion planning algorithms that emphasize the exact combinatorial and purely geometric approach. Motion planning is...
Implementation and Experimentation with Motion Planning Algorithms (2002)
The main charter of this contract is the implementation and experimentation with motion planning algorithms that emphasize the exact combinatorial and purely geometric approach. Motion planning is...
Implementation and Experimentation with Motion Planning Algorithms (2002)
The main charter of this contract is the implementation and experimentation with motion planning algorithms that emphasize the exact combinatorial and purely geometric approach. Motion planning is...
Schwartz,Jacob T., Sharir,Micha
Sponsored in part by Contract EY-76-C-02-3077.
Motion Planning in the Presence of Moving Obstacles (2002)
This paper investigates the computational complexity of planning the motion of a body B in 2-D or 3-D space, so as to avoid collision with moving obstacles of known, easily computed, trajectories....
Translating a Planar Object to Maximize Point Containment (2002)
Agarwal, Pankaj, Hagerup, Torben, Ray, Rahul, Sharir, Micha, Smid, Michiel, Welzl, Emo, ...
Let $C$ be a compact set in $\IR^2$ and let $S$ be a set of $n$ points in $\IR^2$. We consider the problem of computing a translate of $C$ that contains the maximum number, $\kappa^*$, of points...
Lenses in arrangements of pseudo-circles and their applications (2002)
Pach, János, Agarwal, Pankaj K., Nevo, E., Pinchasi, Rom, Sharir, Micha, Smorodinsky, Shakhar
Speeding up the incremental construction of the union of geometric objects in practice (2002)
Eti Ezra, Dan Halperin, Micha Sharir
We present a new incremental algorithm for constructing the union of n triangles in the plane. In our experiments, the new algorithm, which we call the Disjoint-Cover (DC) algorithm, performs...
Translating a planar object to maximize point containment (2002)
Pankaj K. Agarwal, Torben Hagerup, Rahul Ray, Micha Sharir, Michiel Smid, Emo Welzl
Abstract. Let C be a compact set in R
Three-dimensional Euclidean Voronoi diagrams of lines with a fixed number of orientations (2002)
We show that the combinatorial complexity of the Euclidean Voronoi diagram of n lines in R 3 that have at most c distinct orientations is O(c 3 n 2+ε), for any ε> 0. This result is a step...
Lenses in arrangements of pseudocircles and their applications (2002)
Eran Nevo, J Anos Pach, Rom Pinchasi, Micha Sharir, Shakhar Smorodinsky
k A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct...
The 2-center problem with obstacles (2002)
Dan Halperin, Micha Sharir, Ken Goldberg
Given a set S of n points in the plane and a set O of pairwise disjoint simple polygons with a total of m edges, we wish to nd two congruent disks of smallest radius whose union covers S and whose...
Speeding Up the Incremental Construction of the Union of Geometric Objects in Practice (2002)
Eti Ezra, Dan Halperin, Micha Sharir
We present a new incremental algorithm for constructing the union of n triangles in the plane. In our experiments, the new algorithm, which we call the Disjoint-Cover (DC) algorithm, performs signi...
Computing the Detour of Polygonal Curves (2002)
Pankaj K. Agarwal, Pankaj K. Agarwal, Rolf Klein, Rolf Klein, Christian Knauer, Christian Knauer, ...
Let P be a simple polygonal chain in E with n edges. The detour of P between two points, x and y, is the ratio between the length of P between x any y and their Euclidean distance.
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...
Translating a planar object to maximize point containment (2002)
Pankaj K. Agarwal, Torben Hagerup, Rahul Ray, Micha Sharir, Michiel Smid, Emo Welzl
Abstract. Let � be a compact set in Ê and let Ë beasetofÒpoints in Ê.We consider the problem of computing a translate of � that contains the maximum number, � £ , of points of Ë. It is...
Lenses in Arrangements of Pseudo-circles and Their Applications£ (2002)
Pankaj K. Agarwalý, Eran Nevoþ, János Pachü, Rom Pinchasiß, Micha Sharir, Shakhar Smorodinsky
A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct...
Hausdorff Distance under Translation for Points, Disks, (2002)
Pankaj K. Agarwal, Sariel Har-peled, Micha Sharir, Yusu Wang
Let A and B be two sets of balls in R d, d = 2, 3. We measure similarity between A and B by computing the minimum Hausdorff distance between A + t and B, where the minimum is taken either over all...
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...
Polyhedral Voronoi diagrams of polyhedra in three dimensions (2002)
We show that the complexity of the Voronoi diagram of a collection of disjoint polyhedra in general position in 3-space that have n vertices overall, under a convex distance function induced by a...
On the Number of Congruent Simplices in a Point Set (2002)
Pankaj K. Agarwal, Micha Sharir
For 1 k d 1, let f k (n) be the maximum possible number of k-simplices spanned by a set of n points in R that are congruent to a given k-simplex. We prove that f ), for any " > 0, f ), and f...
Hausdorff Distance under Translation for Points, Disks, and Balls (2002)
Pankaj K. Agarwal, Sariel Har-peled, Micha Sharir, Yusu Wang
Let A and B be two sets of balls in R^d, d = 2, 3. We measure similarity between A and B by computing the minimum Hausdorff distance between A+t and B, where the minimum is taken either over all...
Ministère Recherche, Science Et Technologie, Ministère Recherche, Science Et Technologie, ...
34th ACM Symposium
On generalized geometric graphs and pseudolines (2001)
Micha Sharir, Shakhar Smorodinsky
This paper generalizes, extends and simplies many results involving geometric graphs on planar point sets, in the context of pseudoline arrangements. Many of the problems studied here have been the...
Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles (2001)
Adrian Dumitrescu, Micha Sharir
We provide a variety of new results, including upper and lower bounds, as well as simpler proof techniques for the ecient construction of binary space partitions (BSP's) of axis-parallel...
On generalized geometric graphs and pseudolines (2001)
Micha Sharir, Shakhar Smorodinsky
(a) Using a duality transformation on pseudolines, established recently by Agarwal and Sharir [4], we show that any graph G induced by a set of vertices of an arrangement of a nite set of...
Pseudoline arrangements: Duality. algorithms and applications (2001)
Pankaj K. Agarwal, Micha Sharir
A collection L of x-monotone unbounded Jordan curves in the plane is called a family of pseudolines if every pair of curves intersects in at most one point, and the two curves cross each other there....
Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles (2001)
Adrian Dumitrescu, Micha Sharir
We provide a variety of new results, including upper and lower bounds, as well as simpler proof techniques for the ecient construction of binary space partitions (BSP's) of axis-parallel...
Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles (2001)
Adrian Dumitrescu, Micha Sharir
We provide a variety of new results, including upper and lower bounds, as well as simpler proof techniques for the ecient construction of binary space partitions (BSP's) of axis-parallel...
On-line point location in planar arrangements and its applications (2001)
Sariel Har-peled, Micha Sharir
Recently, Har-Peled [HP99b] presented a new randomized technique for online construction of the zone of a curve in a planar arrangement of arcs. In this paper, we present several applications of this...
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...
Pseudo-line Arrangements: Duality, Algorithms, and Applications (2001)
Pankaj K. Agarwal, Micha Sharir
A collection L of n x-monotone unbounded Jordan curves in the plane is called a family of pseudo-lines if every pair of curves intersect in at most one point, and the two curves cross each other...
On-line point location in planar arrangements and its applications (2001)
Sariel Har-peled, Micha Sharir
Recently, Har-Peled [HP99b] presented a new randomized technique for online construction of the zone of a curve in a planar arrangement of arcs. In this paper, we present several applications of this...
Pseudoline arrangements: Duality. algorithms and applications, manuscript (2001)
Pankaj K. Agarwal, Micha Sharir
Abstract A collection L of n x-monotone unbounded Jordan curves in the plane is called a family of pseudo-lines if every pair of curves intersect in at most one point, and the two curves cross each...
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...
On the complexity of arrangements of circles in the plane (2001)
Noga Alon, Hagit Last, Rom Pinchasi, Micha Sharir
Continuing and extending the analysis in a previous paper [9], we establish several combinatorial results on the complexity of arrangements of circles in the plane. The main results are a collection...
An improved bound for k-sets in three dimensions (2000)
Micha Sharir, Shakhar Smorodinsky
We prove that the maximum number of k-sets in a set S of n points in IR 3 is O(nk
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...
Penetration depth of two convex polytopes in 3D (2000)
Pankaj K. Agarwal, Leonidas J. Guibas, Sariel Har-peled, Alexander Rabinovitch, Micha Sharir
Let A and B be two convex polytopes in R 3 with m and n facets, respectively. The penetration depth of A and B, denoted as (A; B), is the minimum distance by which A has to be translated so that A...
Penetration depth of two convex polytopes in 3D (2000)
Pankaj K. Agarwal, Leonidas J. Guibas, Sariel Har-peled, Alexander Rabinovitch, Micha Sharir
Let A and B be two convex polytopes in R 3 with m and n facets, respectively. The penetration depth of A and B, denoted as (A; B), is the minimum distance by which A has to be translated so that A...
Sets In Three, Micha Sharir, Shakhar Smorodinsky
We prove that the maximum number of k-sets in a set S of n points in IR 3 is O(nk 3=2 ). This improves substantially the previous best known upper bound of O(nk 5=3 ) (see [7] and [1]). 1...
Computing the Penetration Depth of Two Convex Polytopes in 3D (2000)
Pankaj K. Agarwal, Leonidas J. Guibas, Sariel Har-peled, Alexander Rabinovitch, Micha Sharir
Let A and B be two convex polytopes in R 3 with m and n facets, respectively. The penetration depth of A and B, denoted as (A; B), is the minimum distance by which A has to be translated so that A...
An Improved Bound for k-Sets in Three Dimensions (2000)
Micha Sharir, Shakhar Smorodinsky, Gábor Tardos
We prove that the maximum number of k-sets in a set S of n points in IR 3 is O(nk 3=2 ). This improves substantially the previous best known upper bound of O(nk 5=3 ) (see [7] and [1]). 1...
On The Complexity of Arrangements of (2000)
Circles In The, Noga Alon, Rom Pinchasi, Micha Sharir
Continuing and extending the analysis in a previous paper [11], we establish several combinatorial results on the complexity of arrangements of circles in the plane. The main results are a collection...
Balanced Lines, Halving Triangles, and the Generalized Lower Bound Theorem (2000)
this paper is to show the relation between the balanced lines problem (A) of [7], some problems involving halving triangles in 3-space, and the Generalized Lower Bound Theorem. This sheds some extra...
Dynamic Data Structures for Fat Ob jects and Their Applications \Lambda (1999)
Alon Efraty, Matthew J. Katzz, Frank Nielsenx, Micha Sharir
Abstract We present several efficient dynamic data structures for point-enclosure queries, involving convex fat objects in R2 or R3. Our planar structures are actually fitted for a more general class...
On k-Sets in Three Dimensions (1999)
Shakhar Smorodinsky, Micha Sharir
We prove that the maximum number of k-sets in a set S of n points in IR 3 , for any fixed k, is O(n 8=3 ). This bound is already known [6], but we believe that our proof is simpler. 1 Introduction...
On-line Point Location in Planar Arrangements and Its Applications (1999)
Sariel Har-peled, Micha Sharir
Recently, Har-Peled [HP99b] presented a new randomized technique for online construction of the zone of a curve in a planar arrangement of arcs. In this paper, we present several applications of this...
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...
Efficient Algorithms for Maximum Regression Depth (1999)
Marc Van Kreveld, Peter Rousseeuw, Micha Sharir, Jack Snoeyink, Bettina Speckmann
We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual...
Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls in R^d (1999)
Shakhar Smorodinsky, Micha Sharir
We prove that the maximum number of geometric permutations, induced by line transversals to a collection of n pairwise disjoint balls in IR d , is \Theta(n d\Gamma1 ). This improves substantially the...
Pipes, Cigars, and Kreplach: The Union of Minkowski Sums in Three Dimensions (1999)
Pankaj K. Agarwal, Micha Sharir
Let\Omega be a set of pairwise-disjoint polyhedral obstacles in R 3 with a total of n vertices, and let B be a ball in R 3 . We show that the combinatorial complexity of the free configuration space...
Dynamic Data Structures for Fat Ob jects and Their Applications \Lambda (1999)
Alon Efraty, Matthew J. Katzz, Frank Nielsenx, Micha Sharir
Abstract We present several efficient dynamic data structures for point-enclosure queries, involving convex fat objects in R2 or R3. Our planar structures are actually fitted for a more general class...
Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications (1999)
Pankaj K. Agarwal, Alon Efrat, Micha Sharir
Abstract Let F be a collection of n bivariate algebraic functions of constant maximum degree.We show that the combinatorial complexity of the vertical decomposition of the <= k-levelof the...
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...
On the Number of Congruent Simplices in a Point Set (1998)
Agarwal, Pankaj K., Sharir, Micha
We derive improved bounds on the number of k-dimensional simplices spanned by a set of n points in R(sup d) that are congruent to a given k-simplex, for k < or = d - 1. Let f(sup d)(sub K)(n) be the...
Davenport-Schinzel Sequences and Their Geometric Applications (1998)
Pankaj K. Agarwal, Micha Sharir
An (n; s) Davenport-Schinzel sequence, for positive integers n and s, is a sequence composed of n distinct symbols with the properties that no two adjacent elements are equal, and that it does not...
Largest placement of one convex polygon inside another (1998)
Pankaj K. Agarwal, Nina Amenta, Micha Sharir
We show that the largest similar copy of a convex polygon P with m edges inside a convex polygon Q with n edges can be computed in O(mn 2 log n) time. We also show that the combinatorial complexity...
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...
Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions (1998)
Jean-daniel Boissonnat, Jean-daniel Boissonnat, Micha Sharir, Micha Sharir, Boaz Tagansky, Boaz Tagansky, ...
The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions. Specifically, if S is a set of n points in general position in...
Efficient algorithms for geometric optimization (1998)
Pankaj K. Agarwal, Micha Sharir
We review the recent progress in the design of efficient algorithms for various problems in geometric optimization. We present several techniques used to attack these problems, such as parametric...
Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions (1998)
Jean-daniel Boissonnat, Micha Sharir, Boaz Tagansky, Mariette Yvinec
The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions. Specifically, if S is a set of n points in general position in IR...
The Discrete 2-Center Problem (1998)
Pankaj K. Agarwal, Micha Sharir, Emo Welzl
We present an algorithm for computing the discrete 2-center of a set P of n points in the plane; that is, computing two congruent disks of smallest possible radius, centered at two points of P ,...
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....
Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls in R^d (1998)
Shakhar Smorodinsky, Micha Sharir
(i) We prove that the maximum number of geometric permutations, induced by line transversals to a collection of n pairwise disjoint balls in IR d , is \Theta(n d\Gamma1 ). This improves substantially...
Arrangements and Their Applications (1998)
Pankaj K. Agarwal, Micha Sharir
The arrangement of a finite collection of geometric objects is the decomposition of the space into connected cells induced by them. We survey combinatorial and algorithmic properties of arrangements...
Efficient Algorithms for Geometric Optimization (1998)
Pankaj K. Agarwal, Micha Sharir
We review the recent progress in the design of efficient algorithms for various problems in geometric optimization. We present several techniques used to attack these problems, such as parametric...
Efficient Algorithms for Geometric Optimization (1998)
Pankaj K. Agarwal, Micha Sharir
We review the recent progress in the design of efficient algorithms for various problems in geometric optimization. We present several techniques used to attack these problems, such as parametric...
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...
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,...
The discrete 2-center problem (1997)
n)-time algorithm for computing the 2-center of a set S of n points in the plane (that is, a pair of congruent disks of smallest radius whose union covers S), improving the previous O(n 2
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...
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...
Approximating Shortest Paths on a Convex Polytope in Three Dimensions (1997)
Pankaj K. Agarwal, Sariel Har-peled, Micha Sharir, Kasturi R. Varadarajan
Given a convex polytope P with n faces in IR 3 , points s; t 2 @P , and a parameter 0 ! " 1, we present an algorithm that constructs a path on @P from s to t whose length is at most (1+ ")d...
The Discrete 2-Center Problem (1997)
Pankaj Agarwal Micha, Pankaj K. Agarwal, Pankaj K. Agarwal, Micha Sharir, Micha Sharir, Emo Welzl, ...
We present an algorithm for computing the discrete 2-center of a set P of n points in the plane; that is, computing two congruent disks of smallest possible radius, centered at two points of P ,...
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....
Ray Shooting Amidst Spheres in Three Dimensions and Related Problems (1997)
We consider the problem of ray shooting amidst spheres in 3-space: given n arbitrary (possibly intersecting) spheres in 3-space and any " ? 0, we show how to preprocess the spheres in time O(n...
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...
Otfried Schwarzkopf, Micha Sharir
Let \Sigma be a collection of n algebraic surface patches of
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...
The Discrete 2-Center Problem (1997)
Pankaj K. Agarwal, Micha Sharir, Emo Welzl
We present an algorithm for computing the discrete 2-center of a set P of n points in the plane; that is, computing two congruent disks of smallest possible radius, centered at two points of P ,...
Efficient motion planning for an L-shaped object (1997)
Dan Halperin, Mark H. Overmars, Micha Sharir
We present an algorithm that solves the following motion-planning problem. Given an L-shaped body L and a 2-dimensional region with n point obstacles, decide whether there is a continuous motion...
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....
Algorithmic Motion Planning (1997)
INTRODUCTION Motion planning is a fundamental problem in robotics. It comes in a variety of forms, but the simplest version is as follows. We are given a robot system B, which may consist of several...
On the Complexity of the Union of Fat Objects in (1997)
The Plane Alon, Alon Efrat, Micha Sharir
We prove a near-linear bound on the combinatorial complexity of the union of n fat convex objects in the plane, each pair of whose boundaries cross at most a constant number of times.
A near-linear algorithm for the planar 2-center problem (1997)
We present an O(n log 9 n)-time algorithm for computing the 2-center of a set S of n points in the plane (that is, a pair of congruent disks of smallest radius whose union covers S), improving 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...
A Near-Linear Algorithm for the Planar Segment Center Problem (1996)
Let P be a set of n points in the plane and let e be a segment of fixed length. The segment center problem is to find a placement of e (allowing translation and rotation) which minimizes the maximum...
The overlay of lower envelopes and its applications (1996)
Micha Sharir, Micha Sharir, Pankaj K. Agarwal, Pankaj K. Agarwal, Pankaj K. Agarwal, Otfried Schwarzkopf, ...
Sharir x Let F and G be two collections of a total of n bivariate algebraic functions of constant maximum degree. The minimization diagrams of F, G are the planar maps obtained by the xy-projections...
Efficient randomized algorithms for some geometric optimization problems (1996)
Pankaj K. Agarwal, Pankaj K. Agarwal, Micha Sharir, Micha Sharir
has been supported by NSF Grants CCR-91-22103 and CCR-93-11127, by a Max-Planck Research
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...
Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications (1996)
Pankaj K. Agarwal, Alon Efrat, Micha Sharir
Let F be a collection of n bivariate algebraic functions of constant maximum degree. We show that the combinatorial complexity of the vertical decomposition of the k-level of the arrangement A(F) is...
Largest Placement of One Convex Polygon inside Another (1996)
Pankaj Agarwal Nina, Pankaj Agarwal, Pankaj K. Agarwal, Pankaj K. Agarwal, Nina Amenta, ...
We show that the largest similar copy of a convex polygon P with m edges inside a convex polygon Q with n edges can be computed in O(mn 2 log n) time. We also show that the combinatorial complexity...
The Overlay of Lower Envelopes and its Applications (1996)
Pankaj K. Agarwal, Otfried Schwarzkopf, Micha Sharir
Let F and G be two collections of a total of n (possibly partially-defined) bivariate algebraic functions of constant maximum degree. The minimization diagrams of F , G are the planar maps obtained...
Excess in Arrangements of Segments (1996)
Let S be a set of n line segments in the plane. The excess of S is the number of repetitions of segments of S along the boundary of the same face of A(S), summed over all segments and faces. We show...
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...
Largest Placement of One Convex Polygon inside Another (1996)
Pankaj Agarwal Nina, Pankaj K. Agarwal, Nina Amenta, Micha Sharir
We show that the largest similar copy of a convex polygon P with m edges inside a convex polygon Q with n edges can be computed in O(mn 2 log n) time. We also show that the combinatorial complexity...
Rectilinear and Polygonal p-Piercing and p-Center Problems (1996)
We consider the p-piercing problem, in which we are given a collection of regions, and wish to determine whether there exists a set of p points that intersects each of the given regions. We give...
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...
Approximating Shortest Paths on a Convex Polytope in Three Dimensions (1996)
Pankaj K. Agarwal, Sariel Har-peled, Micha Sharir, Kasturi R. Varadarajan
Given a convex polytope P with n faces in IR 3 , points s; t 2 @P , and a parameter 0 ! " 1, we present an algorithm that constructs a path on @P from s to t whose length is at most (1+")d...
The Overlay of Lower Envelopes and its Applications (1996)
Pankaj Agarwal, Pankaj K. Agarwal, Otfried Schwarzkopf, Otfried Schwarzkopf, Micha Sharir, Micha Sharir
Let F and G be two collections of a total of n bivariate algebraic functions of constant maximum degree. The minimization diagrams of F , G are the planar maps obtained by the xy-projections of the...
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...
A Subexponential Bound for Linear Programming (1996)
Jiri Matousek, Micha Sharir, Emo Welzl
We present a simple randomized algorithm which solves linear programs with n constraints and d variables in expected minfO(d 2 2 d n); e 2 p d ln(n= p d )+O( p d+ln n) g time in the unit cost model...
Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions (1995)
Boissonnat, Jean-Daniel, Sharir, Micha, Tagansky, Boaz, Yvinec, Mariette
The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions. Specifically, if $ß$ is a set of $n$ points in general position...
Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions (1995)
Boissonnat, Jean-Daniel, Sharir, Micha, Tagansky, Boaz, Yvinec, Mariette
The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions. Specifically, if $ß$ is a set of $n$ points in general position...
Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions (1995)
Boissonnat, Jean-Daniel, Sharir, Micha, Tagansky, Boaz, Yvinec, Mariette
The paper bounds the combinatorial complexity of the Voronoi diagram of a set of points under certain polyhedral distance functions. Specifically, if $ß$ is a set of $n$ points in general position...
Davenport-Schinzel Sequences and Their Geometric Applications (1995)
Pankaj K. Agarwal, Pankaj K. Agarwal, Micha Sharir, Micha Sharir
An (n; s) Davenport--Schinzel sequence, for positive integers n and s, is a sequence composed of n symbols with the properties that no two adjacent elements are equal, and that it does not contain,...
Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications (1995)
Alon Efrat, Micha Sharir, Pankaj K. Agarwal, Pankaj K. Agarwal
Let F be a collection of n bivariate algebraic functions of constant maximum degree. We show that the combinatorial complexity of the vertical decomposition of the k-level of the arrangement A(F) is...
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...
Algorithmic Techniques for Geometric Optimization (1995)
Pankaj K. Agarwal, Micha Sharir
Linear Programming In this section we present an abstract framework that captures both linear programming and many other geometric optimization problems, including computing smallest enclosing balls...
Arrangements in Higher Dimensions: Voronoi Diagrams, Motion Planning, and Other Applications (1995)
. We review recent progress in the study of arrangements of surfaces in higher dimensions. This progress involves new and nearly tight bounds on the complexity of lower envelopes, single cells,...
Efficient Randomized Algorithms for Some Geometric Optimization Problems (1995)
Pankaj K. Agarwal, Micha Sharir
In this paper we first prove the following combinatorial bound, concerning the complexity of the vertical decomposition of the minimization diagram of trivariate functions: Let F be a collection of n...
Arrangements and their Applications in Robotics: Recent Developments (1995)
this paper addresses and survey previous work on these problems. We state the basic new results in Section 3. We exemplify the usefulness of these results by applying them to problems involving robot...
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...
Vertical Decomposition of Arrangements of Hyperplanes in Four Dimensions (1995)
Leonidas J. Guibas, Dan Halperin, Jirí Matousek, Micha Sharir
We show that, for any collection H of n hyperplanes in ! 4 , the combinatorial complexity of the vertical decomposition of the arrangement A(H) of H is O(n 4 log n). The proof relies on properties of...
Almost tight upper bounds for the single cell and zone problems in three dimensions (1995)
We consider the problem of bounding the combinatorial complexity of a single cell in an arrangement of n low-degree algebraic surface patches in 3-space. We show that this complexity is O(n
Algorithms for Weak Epsilon-Nets (1995)
Bernard Chazelle, Herbert Edelsbrunner, David Eppstein, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, ...
In the plane, we can find a weak "-net for convex sets consisting of O(" \Gamma2 ) points, in time O(n" \Gamma2 log 2 (1=")). We can determine the smallest " for which a...
A Near-Quadratic Algorithm for Planning the Motion of a Polygon in a Polygonal Environment (1995)
We consider the problem of planning the motion of an arbitrary k-sided polygonal robot B, free to translate and rotate in a polygonal environment V bounded by n edges. We present an algorithm that...
Algorithms for Weak Epsilon-Nets (1995)
Bernard Chazelle, Herbert Edelsbrunner, David Eppstein, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, ...
In the plane, we can find a weak "-net for convex sets consisting of O(" \Gamma2 ) points, in time O(n" \Gamma2 ). We can determine the smallest " for which a given planar set is...
Algorithmic techniques for geometric optimization (1995)
Pankaj K. Agarwal, Micha Sharir
Abstract. We review the recent progress in the design of e cient algorithms for various problems in geometric optimization. The emphasis in this survey is on the techniques used to attack these...
Reaching a goal with directional uncertainty (1994)
De Berg, Mark, Guibas, L., Halperin, D., Schwarzkopf, Otfried, Sharir, Micha, Teillaud, Monique
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
The Overlay ofLower Envelopes and its Applications (1994)
Pankaj K. Agarwal, Otfried Schwarzkopf, Micha Sharir
Let F and G be two collections of a total of n bivariate algebraic functions of constant maximum degree. The minimization diagrams of F, G are the planar maps obtained by the xy-projections of the...
Applications of parametric searching in geometric optimization (1994)
Pankaj K. Agarwal, Micha Sharir
z Sivan Toledo x
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...
Computing depth orders and related problems (1994)
Pankaj K. Agarwal, Pankaj K. Agarwal, Matthew J. Katz, Matthew J. Katz, Micha Sharir, Micha Sharir
Let K be a set of n non-intersecting objects in 3-space. A depth order of K, if exists, is a linear order! of the objects in K such that if K;L 2 K and K lies vertically below L then K! L. We present...
We consider the problem of bounding the complexity of the lower envelope of n surface patches in 3-space, all algebraic of constant maximum degree, and bounded by algebraic arcs of constant maximum...
Extremal polygon containment problems (1994)
Given a convex polygonal object P and an environment consisting of polygonal obstacles, we seek a placement for the largest copy of P that does not intersect any of the obstacles, allowing...
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...
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...
Computing Depth Orders and Related Problems (1994)
Pankaj K. Agarwal, Matthew J. Katz, Micha Sharir
Let K be a set of n non-intersecting objects in 3-space. A depth order of K, if exists, is a linear order ! of the objects in K such that if K;L 2 K and K lies vertically below L then K ! L. We...
Leonidas Guibas, Micha Sharir, Emo Welzl
Let S be a set of n points in IR d. A set W is a weak "-net for (convex ranges of) S if for any T S containing "n points, the convex hull of T intersects W. We show the existence of...
Fat triangles determine linearly many holes. (1994)
Matoušek, Jiří, Pach, János, Sharir, Micha, Sifrony, Shmuel, Welzl, Emo
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....
An Efficient Multi-Dimensional Searching Technique and its Applications (1993)
Sivan Toledo, Pankaj K. Agarwal, Pankaj K. Agarwal, Micha Sharir, Micha Sharir
This paper describes an improved algorithm for the multi-dimensional searching problem introduced by Megiddo. As a result, we obtain a d O(d) n time deterministic algorithms for linear programming in...
Ray Shooting Amidst Convex Polyhedra and Polyhedral Terrains in Three Dimensions (1993)
Pankaj K. Agarwal, Pankaj K. Agarwal, Micha Sharir, Micha Sharir
We consider the problem of ray shooting in a 3-dimensional scene consisting of m (possibly intersecting) convex polyhedra or polyhedral terrains with a total of n faces, i.e., we want to preprocess...
On the Number of Views of Polyhedral Terrains (1993)
Pankaj K. Agarwal, Pankaj K. Agarwal, Micha Sharir, Micha Sharir
We show that the number of topologically-different orthographic views of a polyhedral terrain with n edges is O(n 5+" ), and that the number of topologically-different perspective views of such...
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...
Optimal Slope Selection via Expanders (1993)
Given n points in the plane and an integer k, the slope selection problem is to find the pair of points whose connecting line has the k-th smallest slope. (In dual setting, given n lines in the...
An Expander-Based Approach to Geometric (1993)
Optimization Matthew Katz, Matthew J. Katz, Micha Sharir
We present a new approach to problems in geometric optimization that are traditionally solved using the parametric searching technique of Megiddo [34].
An invariant property of balls in arrangements of hyperplanes. (1993)
Aronov, Boris, Naiman, Daniel Q., Pach, János, Sharir, Micha
Case-Based BDI Agents: an Effective Approach for Intelligent Search on the World Wide Web (1992)
Cindy Olivia, C.F Chang, C.F Enguix, A.K. Ghose, Micha Sharir, Emo Welzl
We present a simple randomized algorithm which solves linear programs with n constraints and d variables in expected minfO(d 2 2 d n); e 2 p d ln(n= p d )+O( p d+ln n) g time in the unit cost model...
Efficient Hidden Surface Removal for Objects with Small Union Size (1992)
Matthew J. Katz, Mark H. Overmars, Micha Sharir
Let S be a set of n non-intersecting objects in space for which we want to determine the portions visible from some viewing point. We assume that the objects are ordered by depth from the viewing...
Applications of Parametric Searching in Geometric Optimization (1992)
Sivan Toledo, Pankaj K. Agarwal, Pankaj K. Agarwal, Micha Sharir, Micha Sharir
We present several applications in computational geometry of Megiddo's parametric searching technique. These applications include: (1) Finding the minimum Hausdorff distance in the Euclidean...
Arrangements of curves in the plane --- topology, combinatorics, and algorithms. (1992)
Edelsbrunner, Herbert, Guibas, Leonidas, Pach, János, Pollack, Richard, Seidel, Raimund, Sharir, Micha
Tail Estimates for the Space Complexity of Randomised Incremental Algorithms (1992)
Mehlhorn, Kurt, Sharir, Micha, Welzl, Emo, Frederickson, Grag, Graham, Ron, Hochbaum, Dorit S., ...
On Disjoint Concave Chains in Arrangements of (Pseudo) Lines - Corrigendum (1991)
In the paper mentioned in the title [1] we have asserted that the maximum number of edges of m pairwise-disjoint x-monotone concave polygonal chains, contained in the union of n lines or pseudo...
Counting Circular Arc Intersections (1991)
Pankaj Agarwal Marco, Marco Pellegrini, Micha Sharir
In this paper we present efficient algorithms for counting intersections in a collection of circles or circular arcs. We present an algorithm to count intersections in a collection of n circles whose...
Off-line dynamic maintenance of the width of a planar point set (1991)
Pankaj K. Agarwal, Micha Sharir
Agarwal, P.K. and M. Sharir, Off-line dynamic maintenance of the width of a planar point set, Computational Geometry: Theory and Applications 1 (1991) 65-78. In this paper we present an efficient...
Elsevier Counting and cutting cycles of lines and rods in space* (1991)
Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Richard Pollack, Raimund Seidel, Micha Sharir, ...
306 B. Chazelle et al.
On the combinatorial complexity of the space of hyperplane transversals (1990)
Pach, János, Cappell, S.E., Goodman, Jacob E., Pollack, Richard, Sharir, Micha, Wenger, Rephael
On the lower envelope of bivariate functions and its applications (1987)
Pach, János, Edelsbrunner, Herbert, Schwartz, J.T., Sharir, Micha
In this abstract we present a collection of results representing recent progress in the design and analysis of efficient algorithms for planning purely transla-tional collision-free motion of rigid...
Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions
L. Paul Chew, Klara Kedem, Micha Sharir, Boaz Tagansky, Emo Welzl
The combinatorial complexity of the Voronoi diagram of n lines in three dimensions under a convex distance function induced by a polytope with a constant number of edges is shown to be O(n 2 ff(n)...
Motion Planning of a Ball Amid Segments in Three Dimensions
Pankaj K. Agarwal, Micha Sharir
Let S be a set of n pairwise disjoint segments in R 3 , and let B be a ball of radius 1. The free configuration space F of B amid S is the set of all placements of B at which (the interior of) B does...
Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions
L. Paul Chew, Klara Kedem, Micha Sharir, Boaz Tagansky, Emo Welzl
The combinatorial complexity of the Voronoi diagram of n lines in three dimensions under a convex distance function induced by a polytope with a constant number of edges is shown to be O(n 2 ff(n)...
On the Complexity of Many Faces in Arrangements of Pseudo-Segments and of Circles Pankaj K. Agarwal
Pankaj K. Agarwal, Boris Aronov Micha, 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...