Micha Sharir | Academic Influence

Micha Sharir's AcademicInfluence.com Rankings

Micha Sharir

Computer Science

#814

World Rank

#842

Historical Rank

Database

#499

World Rank

#523

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Micha Sharir's Degrees

PhD Computer Science Stanford University
Masters Computer Science Tel Aviv University

Similar Degrees You Can Earn

Why Is Micha Sharir Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Micha Sharir is an Israeli mathematician and computer scientist. He is a professor at Tel Aviv University, notable for his contributions to computational geometry and combinatorial geometry, having authored hundreds of papers.

(See a Problem?)

Micha Sharir's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Davenport-Schinzel sequences and their geometric applications (1995) (931)
On the “piano movers” problem. II. General techniques for computing topological properties of real algebraic manifolds (1983) (925)
On the “piano movers'” problem I. The case of a two‐dimensional rigid polygonal body moving amidst polygonal barriers (1983) (506)
A subexponential bound for linear programming (1992) (439)
Randomized incremental construction of Delaunay and Voronoi diagrams (1990) (412)
On shortest paths in polyhedral spaces (1986) (406)
On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles (1986) (379)
Combinatorial complexity bounds for arrangements of curves and spheres (1990) (351)
Motion planning in the presence of moving obstacles (1985) (323)
On the Piano Movers' Problem: III. Coordinating the Motion of Several Independent Bodies: The Special Case of Circular Bodies Moving Amidst Polygonal Barriers (1983) (314)
Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons (1987) (295)
Nonlinearity of davenport—Schinzel sequences and of generalized path compression schemes (1986) (277)
On the existence and synthesis of multifinger positive grips (2015) (267)
Efficient algorithms for geometric optimization (1998) (267)
Identification of Partially Obscured Objects in Two and Three Dimensions by Matching Noisy Characteristic Curves (1987) (262)
Planning, geometry, and complexity of robot motion (1986) (253)
On the Complexity of Motion Planning for Multiple Independent Objects; PSPACE- Hardness of the "Warehouseman's Problem" (1984) (240)
The upper envelope of voronoi surfaces and its applications (1991) (229)
Arrangements and Their Applications (2000) (229)
A Combinatorial Bound for Linear Programming and Related Problems (1992) (221)
Filling gaps in the boundary of a polyhedron (1995) (207)
Algorithmic motion planning in robotics (1991) (198)
Visibility Problems for Polyhedral Terrains (2018) (196)
Piecewise-linear interpolation between polygonal slices (1994) (196)
Applications of parametric searching in geometric optimization (1992) (191)
Retraction: A new approach to motion-planning (1983) (185)
A Survey of Motion Planning and Related Geometric Algorithms (1988) (180)
Two-Dimensional, Model-Based, Boundary Matching Using Footprints (1986) (177)
Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications (1995) (177)
A Singly Exponential Stratification Scheme for Real Semi-Algebraic Varieties and its Applications (1991) (173)
Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences (2015) (169)
On k-hulls and related problems (1984) (167)
On the Number of Incidences Between Points and Curves (1998) (165)
Algorithmic motion planning (2004) (157)
Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams (2016) (150)
Termination of Probabilistic Concurrent Program (1983) (149)
Quasi-optimal upper bounds for simplex range searching and new zone theorems (1990) (149)
Fat Triangles Determine Linearly Many Holes (1994) (149)
A strong-connectivity algorithm and its applications in data flow analysis. (2018) (148)
Computing the Discrete Fréchet Distance in Subquadratic Time (2012) (146)
Quasi-planar graphs have a linear number of edges (1995) (137)
Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions (1995) (134)
The upper envelope of piecewise linear functions: Algorithms and applications (2015) (131)
Linear time algorithms for visibility and shortest path problems inside simple polygons (2011) (130)
An Automatic Technique for Selection of Data Representations in SETL Programs (1981) (130)
Ray shooting in polygons using geodesic triangulations (1991) (128)
Termination of Probabilistic Concurrent Programs. (1982) (125)
On the general motion planning problem with two degrees of freedom (2015) (123)
Almost tight upper bounds for lower envelopes in higher dimensions (1993) (123)
A Near-Linear Algorithm for the Planar 2-Center Problem (1996) (121)
Repeated Angles in the Plane and Related Problems (1992) (115)
Relative (p,ε)-Approximations in Geometry (2011) (112)
Arrangements of Curves in the Plane - Topology, Combinatorics and Algorithms (2018) (111)
Intersection and Closest-Pair Problems for a Set of Planar Discs (1985) (111)
On the Zone Theorem for Hyperplane Arrangements (1991) (110)
Combinatorial complexity bounds for arrangements of curves and surfaces (2015) (110)
Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes (2010) (109)
Diameter, width, closest line pair, and parametric searching (1992) (108)
Small-size ε-nets for axis-parallel rectangles and boxes (2009) (108)
Efficient hidden surface removal for objects with small union size (1991) (106)
Partial surface and volume matching in three dimensions (1994) (103)
Crossing patterns of semi-algebraic sets (2005) (102)
Incidences in three dimensions and distinct distances in the plane (2010) (99)
Probabilistic temporal logics for finite and bounded models (1984) (98)
New bounds for lower envelopes in three dimensions, with applications to visibility in terrains (1993) (98)
The overlay of lower envelopes and its applications (1996) (94)
An expander-based approach to geometric optimization (1993) (94)
Separating two simple polygons by a sequence of translations (2015) (94)
On the number of crossing-free matchings, (cycles, and partitions) (2006) (92)
The complexity and construction of many faces in arrangements of lines and of segments (1990) (92)
Triangles in space or building (and analyzing) castles in the air (1990) (89)
Online conflict-free coloring for intervals (2005) (88)
Simple Proofs of Classical Theorems in Discrete Geometry via the Guth–Katz Polynomial Partitioning Technique (2011) (87)
Computing the geodesic center of a simple polygon (2011) (86)
An Improved Bound for k-Sets in Three Dimensions (2000) (85)
Efficient randomized algorithms for some geometric optimization problems (1995) (83)
Penetration Depth of Two Convex Polytopes in 3D (2000) (83)
Structural Analysis: A New Approch to Flow Analysis in Optimizing Compilers (2015) (82)
New results on shortest paths in three dimensions (2004) (82)
Computing envelopes in four dimensions with applications (1994) (81)
Computing the link center of a simple polygon (2011) (80)
Selecting distances in the plane (1990) (79)
Improved bounds on weak ε-nets for convex sets (1993) (79)
Computing the Smallest K-enclosing Circle and Related Problems (1993) (78)
On levels in arrangements of lines, segments, planes, and triangles (1997) (78)
Computing a face in an arrangement of line segments (1991) (78)
Counting and cutting cycles of lines and rods in space (1990) (78)
An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space (1990) (77)
Efficient Detection of Intersections among Spheres (1983) (75)
Line Transversals of Balls and Smallest Enclosing Cylinders in Three Dimensions (1997) (75)
The Discrete 2-Center Problem (1997) (74)
The union of convex polyhedra in three dimensions (1993) (74)
On shortest paths amidst convex polyhedra (1987) (74)
Points and triangles in the plane and halving planes in space (1990) (73)
Rectilinear and polygonal p-piercing and p-center problems (1996) (73)
The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2 (1990) (72)
Combinatorial Problems in Computational Geometry (2003) (72)
On the zone of a surface in a hyperplane arrangement (1991) (71)
On the Piano Movers''Problem V: The Case of a Rod Moving in Three-Dimensional Space amidst Polyhedra (1984) (68)
Verification of Probabilistic Programs (1984) (68)
Cutting Circles into Pseudo-Segments and Improved Bounds for Incidences% and Complexity of Many Faces (2002) (68)
Polynomials vanishing on grids: The Elekes-Rónyai problem revisited (2014) (68)
Lenses in arrangements of pseudo-circles and their applications (2004) (67)
Unit Distances in Three Dimensions (2011) (66)
Almost linear upper bounds on the length of general davenport—schinzel sequences (1987) (64)
Counting Triangulations of Planar Point Sets (2009) (63)
An Optimal-Time Algorithm for Shortest Paths on a Convex Polytope in Three Dimensions (2006) (63)
The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis (2011) (63)
Castles in the air revisited (1992) (63)
On Translational Motion Planning of a Convex Polyhedron in 3-Space (1997) (62)
Algorithms for bichromatic line-segment problems and polyhedral terrains (1994) (62)
On Range Searching with Semialgebraic Sets II (2012) (62)
On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space (1987) (62)
On lines, joints, and incidences in three dimensions (2009) (61)
Combinatorial Geometry and Its Algorithmic Applications (2008) (60)
On Lines and Joints (2009) (60)
Dynamic data structures for fat objects and their applications (1997) (59)
On the Union of Fat Wedges and Separating a Collection of Segments By a Line (1993) (59)
On the complexity of the union of fat objects in the plane (1997) (59)
Dynamic Planar Voronoi Diagrams for General Distance Functions and Their Algorithmic Applications (2016) (58)
The complexity of many cells in arrangements of planes and related problems (2015) (58)
Polynomials Vanishing on Cartesian Products: The Elekes-Szabó Theorem Revisited (2015) (58)
A Singly-Expenential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications (1989) (57)
Experience with the SETL Optimizer (1983) (55)
Almost tight upper bounds for the single cell and zone problems in three dimensions (1994) (55)
Applications of a New Space Partitioning Technique (1991) (55)
Pipes, Cigars, and Kreplach: the Union of Minkowski Sums in Three Dimensions (1999) (53)
Approximating shortest paths on a convex polytope in three dimensions (1997) (52)
An Efficient and Simple Motion Planning Algorithm for a Ladder Amidst Polygonal Barriers (1987) (52)
A simple output-sensitive algorithm for hidden surface removal (1992) (51)
An efficient and simple motion planning algorithm for a ladder moving in two-dimensional space amidst polygonal barriers (extended abstract) (1985) (51)
Implicitly representing arrangements of lines or segments (2011) (51)
An efficient algorithm for planning collision-free translational motion of a convex polygonal object in 2-dimensional space amidst polygonal obstacles (1985) (51)
Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier (2016) (50)
Automatic data structure selection in SETL (1979) (50)
Applications of a new space-partitioning technique (1993) (50)
Coordinated motion planning for two independent robots (1991) (50)
Optimal Slope Selection Via Expanders (1993) (48)
Largest Placement of One Convex Polygon Inside Another (1998) (48)
Lines in space - combinatorics, algorithms and applications (1989) (48)
Probabilistic Propositional Temporal Logics (1986) (48)
Red-Blue intersection detection algorithms, with applications to motion planning and collision detection (1990) (48)
State of the Union (of geometric objects) (2008) (47)
Colored intersection searching via sparse rectangular matrix multiplication (2006) (47)
State of the Union ( of Geometric Objects ) : A Review ∗ (2007) (46)
Computing Depth Orders for Fat Objects and Related Problems (1995) (46)
Arrangements and their applications in robotics: recent developments (1995) (45)
Efficient Colored Orthogonal Range Counting (2008) (45)
Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications (2012) (45)
On the performance of the ICP algorithm (2008) (45)
Voronoi diagrams of lines in 3-space under polyhedral convex distance functions (1995) (45)
Random triangulations of planar point sets (2006) (45)
Approximating shortest paths on a convex polytope in three dimensions (1996) (45)
Distinct distances on two lines (2013) (45)
Output-sensitive hidden surface removal (1989) (44)
Improved bounds for incidences between points and circles (2012) (44)
Cutting algebraic curves into pseudo-segments and applications (2016) (44)
Coresets forWeighted Facilities and Their Applications (2006) (44)
Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique (2011) (43)
Motion Planning for a Convex Polygon in a Polygonal Environment (1999) (43)
Top-Down Analysis of Path Compression (2005) (42)
Pseudo-line arrangements: duality, algorithms, and applications (2002) (42)
Improved Bounds for 3SUM, K-SUM, and Linear Degeneracy (2015) (42)
Improved Bounds for the Union of Locally Fat Objects in the Plane (2014) (42)
On the Two-Dimensional Davenport Schinzel Problem (2018) (41)
Counting Plane Graphs: Flippability and Its Applications (2010) (40)
Approximation and exact algorithms for minimum-width annuli and shells (1999) (40)
A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment (1996) (40)
Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic Õ(n5/3) Time (2017) (39)
Lines in space: Combinatorics and algorithms (1996) (39)
Precise Implementation of Cad Primitives using Rational Parameterizations of Standard Surfaces (1984) (39)
On the shortest paths between two convex polyhedra (2018) (38)
Computing the Detour and Spanning Ratio of Paths, Trees, and Cycles in 2D and 3D (2008) (38)
Efficient algorithms for planning purely translational collision-free motion in two and three dimensions (1987) (38)
A near-linear algorithm for the planar segment-center problem (1994) (38)
On the sum of squares of cell complexities in hyperplane arrangements (1991) (37)
Kinetic and dynamic data structures for closest pair and all nearest neighbors (2008) (37)
The complexity of many faces in arrangements of lines of segments (1988) (37)
Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls in Rd (1999) (37)
On levels in arrangements of lines (1998) (37)
Planar geometric location problems (1994) (36)
On the Complexity of the Union of Fat Convex Objects in the Plane (2000) (36)
The 2-center problem with obstacles (2000) (36)
Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles (2009) (35)
On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm (1991) (35)
Binary Space Partitions for Axis-Parallel Segments, Rectangles, and Hyperrectangles (2004) (35)
An Algorithm for Generalized Point Location and its Applications (1990) (35)
Ray Shooting Amidst Convex Polygons in 2D (1996) (34)
Three dimensional euclidean Voronoi diagrams of lines with a fixed number of orientations (2002) (34)
Polyhedral Voronoi Diagrams of Polyhedra in Three Dimensions (2002) (34)
Improved lower bounds on the length of Davenport-Schinzel sequences (1988) (33)
Efficient Algorithms for Maximum Regression Depth (1999) (33)
Ray Shooting amidst Convex Polyhedra and Polyhedral Terrains in Three Dimensions (1996) (33)
Arrangements of Curves in the Plane - Topology, Combinatorics, and Algorithms (1988) (33)
Incidences between points and lines on a two-dimensional variety (2015) (33)
Weak ε-nets and interval chains (2008) (32)
Lines in space-combinators, algorithms and applications (1989) (32)
Some Observations Concerning Formal Differentiation of Set Theoretic Expressions (2011) (32)
Union of Random Minkowski Sums and Network Vulnerability Analysis (2013) (32)
The partition technique for overlays of envelopes (2002) (32)
Counting colors in boxes (2007) (31)
On empty convex polygons in a planar point set (2004) (31)
Intersecting Line Segments, Ray Shooting, and Other Applications of Geometric Partitioning Techniques (1988) (31)
Incidences between Points and Lines in R^4 (2014) (31)
The Shortest Watchtower and Related Problems for Polyhedral Terrains (2018) (31)
Bi-criteria linear-time approximations for generalized k-mean/median/center (2007) (31)
Large Complete Bipartite Subgraphs In Incidence Graphs Of Points And Hyperplanes (2007) (31)
Partial surface matching by using directed footprints (1996) (31)
Topological Graphs with No Large Grids (2005) (30)
Combinatorics and Algorithms of Arrangements (1993) (30)
A Hyperplane Incidence Problem with Applications to Counting Distances (1990) (30)
Constructing Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes in Space (2009) (30)
On the Boundary of the Union of Planar Convex Sets (1999) (30)
Efficient motion planning for an L-shaped object (1992) (30)
On Joints in Arrangements of Lines in Space and Related Problems (1994) (30)
Computing a Segment Center for a Planar Point Set (1993) (28)
The Common Exterior of Convex Polygons in the Plane (1997) (28)
Incidences between points and circles in three and higher dimensions (2002) (28)
The union of congruent cubes in three dimensions (2001) (27)
Kinetic and dynamic data structures for convex hulls and upper envelopes (2005) (27)
Extremal structure in operator spaces (1973) (27)
On arrangements of Jordan arcs with three intersections per pair (2018) (27)
Characterization and properties of extreme operators intoC(Y) (1972) (27)
On Levels in Arrangements of Lines, Segments, Planes, and Triangles% (1998) (27)
3-Dimensional Euclidean Voronoi Diagrams of Lines with a Fixed Number of Orientations (2003) (27)
Off-line Dynamic Maintenance of the Width of a Planar Point Set (1991) (27)
The Number of Congruent Simplices in a Point Set (2002) (27)
On the number of views of polyhedral terrains (1993) (26)
Algorithms for center and Tverberg points (2004) (26)
Efficient generation of k-directional assembly sequences (1996) (26)
Counting circular arc intersections (1991) (26)
Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting (2006) (26)
Hausdorff distance under translation for points and balls (2003) (26)
Ray Shooting Amidst Spheres in Three Dimensions and Related Problems (1997) (25)
Geometric applications of Davenport-Schinzel sequences (1986) (25)
On the Complexity of Arrangements of Circles in the Plane (2001) (25)
Concurrent Probabilistic Programs, Or: How to Schedule if You Must (1985) (25)
Onk-sets in arrangements of curves and surfaces (1991) (25)
An elementary approach to lower bounds in geometric discrepancy (1995) (25)
Minkowski Sums of Monotone and General Simple Polygons (2006) (25)
The Clarkson-Shor technique revisited and extended (2001) (24)
An Improved Bound for Joints in Arrangements of Lines in Space (2005) (24)
Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices, and Their Applications (2017) (24)
Improved bound for the union of fat triangles (2011) (24)
Geometrically aware communication in random wireless networks (2004) (24)
Kinetic stable Delaunay graphs (2010) (24)
The number of edges of many faces in a line segment arrangement (1992) (24)
Planar geometric location problems and maintaining the width of a planar set (1991) (24)
On critical orientations in the kedem-sharir motion planning algorithm (1997) (24)
On degrees in random triangulations of point sets (2010) (24)
Distinct distances in three and higher dimensions (2003) (24)
Point-line incidences in space (2002) (24)
Counting Plane Graphs: Cross-Graph Charging Schemes (2012) (23)
On approximate halfspace range counting and relative epsilon-approximations (2007) (23)
Sets with few distinct distances do not have heavy lines (2014) (23)
Near-Linear Approximation Algorithms for Geometric Hitting Sets (2009) (23)
Exact and Approximation Algorithms for Minimum-Width Cylindrical Shells (2000) (23)
Solution of Scott's Problem on the Number of Directions Determined by a Point Set in 3-Space (2004) (23)
An automatic motion planning system for a convex polygonal mobile robot in 2-dimensional polygonal space (1988) (23)
Dynamic Time Warping and Geometric Edit Distance (2018) (22)
Online Point Location in Planar Arrangements and Its Applications (2001) (22)
On translational motion planning in 3-space (1994) (22)
Computing the Detour of Polygonal Curves (2002) (22)
Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions (2007) (21)
External Polygon Containment Problems (1994) (21)
The Elekes–Szabó Theorem in four dimensions (2016) (21)
Translating a Planar Object to Maximize Point Containment (2002) (21)
Improved Bounds on Weak epsilon-Nets for Convex Sets (1995) (21)
Laplace Transform Inversion of Rational Functions (1971) (20)
Computing the volume of the union of cubes (2007) (20)
Circle Shooting in a Simple Polygon (1993) (20)
Approximate Halfspace Range Counting (2010) (20)
An Efficient Multi-Dimensional Searching Technique and itsApplications (1993) (20)
Selecting Heavily Covered Points (1994) (20)
Computing Depth Orders and Related Problems (1994) (20)
Incidences between Points and Lines in Three Dimensions (2015) (20)
Largest Placements and Motion Planning of a Convex Polygon (1996) (19)
On the Union of κ-Round Objects in Three and Four Dimensions (2004) (19)
Object recognition by three‐dimensional curve matching (1986) (19)
Davenport{schinzel Sequences and Their Geometric Applications 1 Davenport{schinzel Sequences and Their Geometric Applications (1995) (19)
k-Sets in Four Dimensions (2006) (19)
Near-quadratic bounds for the motion planning problem for a polygon in a polygonal environment (1993) (18)
Storing line segments in partition trees (1990) (18)
Sphere-of-influence graphs in higher dimensions (1994) (18)
On the number of directions determined by a three-dimensional points set (2004) (18)
Vertical decomposition of arrangements of hyperplanes in four dimensions (1995) (18)
Extremal problems on triangle areas in two and three dimensions (2007) (18)
On minima of function, intersection patterns of curves, and davenport-schinzel sequences (1985) (17)
Slimming down by adding; selecting heavily covered points (1990) (17)
A counterexample on extreme operators (1976) (17)
Speeding up the incremental construction of the union of geometric objects in practice (2002) (17)
Guarding a Terrain by Two Watchtowers (2005) (17)
Vertical decomposition of a single cell in a three-dimensional arrangement of surfaces and its applications (1996) (17)
Termination of probabilistic concurrent programs: (extended abstract) (1982) (17)
Counting and representing intersections among triangles in three dimensions (2004) (16)
Semialgebraic Range Reporting and Emptiness Searching with Applications (2009) (16)
A non-nice extreme operator (1977) (16)
Lenses in arrangements of pseudo-circles and their applications (2002) (16)
Theoretical and experimental studies using a multifinger planar manipulator (1988) (16)
On Disjoint Concave Chains in Arrangements of (Pseudo) Lines (1994) (16)
The Number of Unit-Area Triangles in the Plane: Theme and Variation (2015) (16)
The Overlay of Minimization Diagrams in a Randomized Incremental Construction (2011) (16)
Range Minima Queries with Respect to a Random Permutation, and Approximate Range Counting (2011) (16)
The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection (2013) (16)
Similar simplices in a d-dimensional point set (2007) (15)
Ray shooting amid balls, farthest point from a line, and range emptiness searching (2005) (15)
A new efficient motion-planning algorithm for a rod in polygonal space (1986) (15)
Almost Tight Bounds for Eliminating Depth Cycles in Three Dimensions (2015) (15)
Vertical Decomposition of a Single Cell in a Three-Dimensional Arrangement of Surfaces (1997) (15)
Optimal Cover of Points by Disks in a Simple Polygon (2010) (15)
On the number of regular vertices of the union of jordan regions (1998) (15)
The Discrete Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection (2013) (15)
Distinct Distances from Three Points (2013) (15)
On the Complexity of Many Faces in Arrangements of Pseudo-Segments and Circles (2003) (15)
Fat triangles determine linearly many holes (computational geometry) (1991) (14)
The Simplex Algorithm in Dimension Three (2003) (14)
The 2-center problem in three dimensions (2010) (14)
Algorithmic Techniques for Geometric Optimization (1995) (14)
Incidences between points and lines in R4: Extended Abstract (2014) (14)
Generalized Voronoi diagrams for a ladder: II. Efficient construction of the diagram (2018) (14)
Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles (2001) (14)
Lines Avoiding Unit Balls in Three Dimensions (2005) (14)
A Nearly Quadratic Bound for Point-Location in Hyperplane Arrangements, in the Linear Decision Tree Model (2018) (13)
Reporting Neighbors in High-Dimensional Euclidean Space (2013) (13)
Arrangements of surfaces in higher dimensions (1999) (13)
A Note on the Papadimitriou-Silverberg Algorithm for Planning Optimal Piecewise-Linear Motion of a Ladder (2019) (13)
On Bivariate Smoothness Spaces Associated with Nonlinear Approximation (2004) (13)
Improved Combinatorial Bounds and Efficient Techniques for Certain Motion Planning Problems with Three Degrees of Freedom (1992) (13)
On Triple Intersections of Three Families of Unit Circles (2014) (13)
The Clarkson–Shor Technique Revisited and Extended (2003) (13)
Repeated Angles in Three and Four Dimensions (2005) (13)
The overlay of lower envelopes in three dimensions and its applications (1995) (13)
Incidences Between Points and Lines on Two- and Three-Dimensional Varieties (2016) (12)
Decomposing Arrangements of Hyperplanes: VC-Dimension, Combinatorial Dimension, and Point Location (2017) (12)
Reaching a Goal with Directional Uncertainty (1993) (12)
E cient Algorithms for Geometric Optimization (1998) (12)
Tail Estimates for the Efficiency of Randomized Incremental Algorithms for Line Segment Intersection (1993) (12)
A Nearly Quadratic Bound for the Decision Tree Complexity of k-SUM (2017) (12)
Stabbing pairwise intersecting disks by five points (2018) (12)
Incidences with curves in R^d (2015) (12)
Ray shooting and stone throwing with near-linear storage (2005) (12)
A faster algorithm for the discrete Fréchet distance under translation (2015) (11)
Improved bounds on the complexity of many faces in arrangements of segments (1992) (11)
A kinetic triangulation scheme for moving points in the plane (2010) (11)
Optical computational geometry (1992) (11)
Selecting Points that are Heavily Covered by Pseudo-Circles, Spheres or Rectangles (2004) (11)
Transformational Derivation of a Garbage Collection Algorithm (1982) (11)
Arrangements in Higher Dimensions: Voronoi Diagrams, Motion Planning, and Other Applications (1995) (11)
Finding the Maximal Empty Rectangle Containing a Query Point (2011) (11)
On the ICP algorithm (2006) (11)
On the lower envelope of bivariate functions and its applications (1987) (11)
Finding the maximal empty disk containing a query point (2012) (11)
Combinatorial Geometry with Algorithmic Applications The Alcala Lectures János Pach (2008) (11)
Curve-sensitive cuttings (2003) (11)
A new proof of the Maurey-Pisier theorem (1979) (11)
Cutting Triangular Cycles of Lines in Space (2003) (10)
A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space (1987) (10)
Non-Degenerate Spheres in Three Dimensions (2011) (10)
Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions (2014) (10)
Epsilon-Nets for Halfspaces Revisited (2014) (10)
Balanced lines, halving triangles, and the generalized lower bound theorem (2001) (10)
Incidences Between Points and Lines in $${\mathbb {R}}^4$$R4 (2017) (10)
Stabbing Convex Polygons with a Segment or a Polygon (2008) (10)
k-sets and random hulls (1993) (10)
On the number of congruent simplices in a point (2001) (10)
The design of a global optimizer (1979) (10)
Extremal Configurations and Levels in Pseudoline Arrangements (2003) (10)
Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks (2004) (10)
Relative (p,epsilon)-Approximations in Geometry (2009) (10)
An Improved Bound for k-Sets in Four Dimensions (2010) (10)
Shrinking Minimal Systems and Complementation oflpnSpaces in Reflexive Banach Spaces (1979) (9)
Hausdor Distance under Translation for Points, Disks, and Balls (2002) (9)
Incidences with curves and surfaces in three dimensions, with applications to distinct and repeated distances (2016) (9)
Merging visibility maps (1990) (9)
On Overlays and Minimization Diagrams (2006) (9)
On planar intersection graphs with forbidden subgraphs (2008) (9)
How to Find a Point in the Convex Hull Privately (2020) (9)
Output-sensitive construction of the union of triangles (2004) (9)
Incidences with Curves in ℝ d (2015) (9)
Eliminating Depth Cycles Among Triangles in Three Dimensions (2016) (9)
Recent Developments in the Theory of Arrangements of Surfaces (1999) (9)
Some modified algorithms for Dijkstra's longest upsequence problem (1982) (8)
The Union of Congruent Cubes in Three Dimensions (2003) (8)
Reporting intersecting pairs of convex polytopes in two and three dimensions (2002) (8)
Relative ε-Approximations in Geometry ∗ (2006) (8)
On Graphs That Do Not Contain The Cube And Related Problems (2005) (8)
Stable Delaunay Graphs (2015) (8)
Eppstein's bound on intersecting triangles revisited (2008) (8)
On the number of unit-area triangles spanned by convex grids in the plane (2015) (8)
On the Piano Movers' Problem: IV. Various Decomposable Two-dimensional Motion Planning Problems (2015) (8)
On the union of fat tetrahedra in three dimensions (2009) (8)
On translational motion planning in three dimensions (1994) (7)
On the complexity of many faces in arrangements of circles (2001) (7)
Algorithms for center and Tverberg points (2008) (7)
Finding Axis-Parallel Rectangles of Fixed Perimeter or Area Containing the Largest Number of Points (2019) (7)
Cell Complexities in Hyperplane Arrangements (2004) (7)
Ray shooting amidst convex polytopes in three dimensions (1993) (7)
On K-Sets in Arrangements of Curves and Surfaces (2018) (7)
Dominance Product and High-Dimensional Closest Pair under L_infty (2016) (7)
On Radial Isotropic Position: Theory and Algorithms (2020) (7)
A tight bound for the number of different directions in three dimensions (2003) (7)
Linear Data Structures for Fast Ray-Shooting amidst Convex Polyhedra (2009) (7)
Minimum Partial-Matching and Hausdorff RMS-Distance under Translation: Combinatorics and Algorithms (2014) (7)
Point–Line Incidences in Space (2004) (7)
Intersection and decomposition algorithms for arrangements of curves in the plane (1989) (7)
Combinatorial Geometry with Algorithmic Applications (2006) (7)
Incidences with Curves in R (2016) (7)
Pseudoline Arrangements : Duality , Algorithms , and Applications (2001) (7)
Distinct distances between points and lines (2015) (7)
A note on extreme elements in (1974) (7)
Line Transversals of Convex Polyhedra in R3 (2009) (7)
Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets: Collinearity Testing and Related Problems (2020) (6)
The Decision Tree Complexity for k-SUM is at most Nearly Quadratic (2016) (6)
Finding Maximally Consistent Sets of Halfspaces (1993) (6)
Common Tangents and Common Transversals (2018) (6)
Distinct and repeated distances on a surface and incidences between points and spheres (2016) (6)
A Single Cell in an Arrangement of Convex Polyhedra in ${\Bbb R}^3$ (2007) (6)
CIRCULAR VISIBILITY FROM A POINT IN A SIMPLE POLYGON (1993) (6)
Improved Bounds for Geometric Permutations (2010) (6)
On neighbors in geometric permutations (2002) (5)
Approximating the $k$-Level in Three-Dimensional Plane Arrangements (2016) (5)
On Ray Shooting for Triangles in 3-Space and Related Problems (2021) (5)
Efficient Randomized Algorithms for Some Geometric Optimization (1995) (5)
The Minkowski sum of a simple polygon and a segment (2003) (5)
On a Single Cell in an Arrangement of Convex Polyhedra in R 3 ∗ (2006) (5)
The combinatorial complexity of hyperplane transversals (1990) (5)
Tail estimates for the space complexity of randomized incremental algorithms (1992) (5)
Incidences between Points and Circles in Three and Higher Dimensions (2005) (5)
Generalized Voronoi Diagrams for Moving a Ladder: I. Topological Analysis (2015) (5)
Incidences with Curves in $\mathbb{R}^d$ (2016) (5)
On the general motion-planning problem with two degrees of freedom (1989) (5)
Circular visibility of a simple polygon from a fixed point (1993) (5)
Robot motion planning (1995) (5)
Incidences between points on a variety and planes in R^3 (2016) (5)
Formal Integration: A Program Transformation Technique (1981) (5)
On the union of κ-round objects (2004) (5)
Distinct distances between a collinear set and an arbitrary set of points (2016) (5)
Finding effective “force targets” for two-dimensional, multifinger frictional grips (2015) (5)
Motion Planning and Related Geometric Algorithms in Robotics (2010) (4)
Union of Hypercubes and 3D Minkowski Sums with Random Sizes (2021) (4)
On lattices, distinct distances, and the Elekes-Sharir framework (2013) (4)
An Improved Bound on the Number of Unit Area Triangles (2009) (4)
Hausdorff distance under translation for points and balls (2010) (4)
Triangles and Girth in Disk Graphs and Transmission Graphs (2019) (4)
On regular vertices on the union of planar objects (2007) (4)
Output-Sensitive Tools for Range Searching in Higher Dimensions (2013) (4)
On lines avoiding unit balls in three dimensions (2004) (4)
Data Flow Analysis of Applicative Programs (1981) (4)
Dominance Products and Faster Algorithms for High-Dimensional Closest Pair under L∞ (2016) (4)
General techniques for approximate incidences and their application to the camera posing problem (2019) (4)
Computing Maximally Separated Sets in the Plane (2006) (4)
Incidences between points and curves with almost two degrees of freedom (2020) (4)
Finding the Largest Disk Containing a Query Point in Logarithmic Time with Linear Storage (2013) (4)
The caratheodory number for thek-core (1990) (4)
On Regular Vertices of the Union of Planar Convex Objects (2009) (4)
Ray Shooting and Stone Throwing (2003) (3)
Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems (2022) (3)
Space-Aware Reconfiguration (2020) (3)
Almost Tight Bounds for Eliminating Depth Cycles in Three Dimensions (2017) (3)
Arrangements of Surfaces in Higher Dimensions: Envelopes Single Cells and Other Recent Developments (1993) (3)
Voronoi diagrams on planar graphs , and computing the diameter in deterministic Õ ( n 5 / 3 ) time Pawe (2017) (3)
The power of geometric duality and Minkowski sums in optical computational geometry (1993) (3)
Approximate Minimum-Weight Matching with Outliers under Translation (2018) (3)
The complexity of the outer face in arrangements of random segments (2008) (3)
Approximate Nearest Neighbor Search Amid Higher-Dimensional Flats (2017) (3)
Concurrent Probabilistic Program, or: How to Schedule if You Must (1983) (3)
Computational Geometry Column 65 (2017) (3)
On Generalized Geometric Graphs and Pseudolines (2001) (3)
Partial-Matching RMS Distance Under Translation: Combinatorics and Algorithms (2018) (2)
Retraction: A New Approach to Motion-Planning (Extended Abstract) (1983) (2)
On the overlay of envelopes in four dimensions (2002) (2)
Radial Points in the Plane (2001) (2)
Approximation Algorithms for Minimum-Width Annuli and Shells (2000) (2)
A note on distinct distances in rectangular lattices (2014) (2)
Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model (2022) (2)
Dynamic Time Warping: Breaking the Quadratic Barrier (2016) (2)
Decomposing the Complement of the Union of Cubes in Three Dimensions (2021) (2)
Computing a Center-Transversal Line (2006) (2)
Output Sensitive Algorithms for Approximate Incidences and Their Applications (2020) (2)
Delaunay Triangulations of Degenerate Point Sets (2015) (2)
Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions (2001) (2)
Reporting neighbors in high-dimensional Euclidean spaces (2013) (2)
35th International Symposium on Computational Geometry, SoCG 2019, June 18-21, 2019, Portland, Oregon, USA (2019) (2)
An improved technique for output-sensitive hidden surface removal (1994) (2)
Incidences between points and non-coplanar circles (2012) (2)
Finding the largest Empty Disk containing a Query Point (2013) (1)
On rich points and incidences with restricted sets of lines in 3-space (2020) (1)
On the Complexity of the Discrete Fréchet Distance under L 1 and L ∞ (2015) (1)
The Number of Unit-Area Triangles in the Plane: Theme and Variation (2016) (1)
Throwing a Sofa Through the Window (2021) (1)
Pipes, Cigars, and Kreplach: the Union of Minkowski Sums in Three Dimensions (2000) (1)
Distinct Distances in Three Dimensions (2001) (1)
The Discrete and Semi-continuous Fr\'echet Distance with Shortcuts via Approximate Distance Counting and Selection Techniques (2013) (1)
On Distinct Distances and Incidences: Elekes's Transformation and the New Algebraic Developments ∗ (2010) (1)
Motion planning of a ball amid segments in three dimensions (1999) (1)
Algorithms for Weak "-nets (1995) (1)
Union of Random Minkowski Sums and Network Vulnerability Analysis (2014) (1)
Contemporary Mathematics State of the Union ( of Geometric Objects ) (2007) (1)
Implementation of a motion planning system in three dimensions (1993) (1)
The interface between computational and combinatorial geometry (2005) (1)
On Approximate Halfspace Range Counting and Relative "-Approximations (2007) (1)
Homotheties and incidences (2017) (1)
Bottleneck Matching in the Plane (2022) (1)
On Arrangement of Jordan Arcs with Three Intersection per Pair (1989) (1)
Intersection Searching amid Tetrahedra in Four Dimensions (2022) (1)
An invariant property of balls in arrangements of hyperplanes (1993) (1)
Arrangements in Geometry: Recent Advances and Challenges (2007) (1)
Acknowledgments Discussions With (1996) (1)
On the Union Complexity of Diametral Disks (2013) (1)
Subquadratic Algorithms for Some \textsc{3Sum}-Hard Geometric Problems in the Algebraic Decision Tree Model (2021) (1)
Covering Points by Hyperplanes and Related Problems (2022) (1)
Efficient algorithms for optimization problems involving distances in a point set (2021) (1)
The Random Edge Rule on Three-Dimensional Linear Programs (2003) (1)
Excess in Arrangements of Segments (1996) (1)
Sylvester-Gallai problem: The beginnings of combinatorial geometry (2008) (1)
Duality-based approximation algorithms for depth queries and maximum depth (2020) (1)
Intersection Searching Amid Tetrahedra in 4-Space and Efficient Continuous Collision Detection (2022) (1)
ε-Nets for Halfspaces Revisited ∗ (2014) (1)
Fast Composition of Sparse Maps (1982) (0)
Dagstuhl-seminar 01121, ''computational Geometry'' Three-dimensional Mesh Generation for Domains with Small Angles a Separation Bound for Real Algebraic Expressions (0)
Incidences and their relatives: From Szemerédi and Trotter to cutting lenses (2008) (0)
C O ] 2 0 A ug 2 00 4 The Simplex Algorithm in Dimension Three 1 (2021) (0)
On rich lenses in planar arrangements of circles and related problems (2020) (0)
Algorithm Derivation by Transformations (reprint) (2010) (0)
Data Flow Analysis of Applicative ~rograms (2005) (0)
Incidences with curves in three dimensions (2020) (0)
On Reverse Shortest Paths in Geometric Proximity Graphs (2022) (0)
J ul 2 02 0 Incidences with curves in three dimensions ∗ (2021) (0)
50 ALGORITHMIC MOTION PLANNING (2016) (0)
Simple Proofs of Classical Theorems in Discrete Geometry via the Guth–Katz Polynomial Partitioning Technique (2012) (0)
Termination of Probabilistic Programs (1983) (0)
Grigni : [ 22 ] Algorithms for Weak "-Nets (0)
J an 2 00 3 The Random Edge Rule on Three-Dimensional Linear Programs 1 ( extended abstract ) (2022) (0)
SERIE B INFORMATIK Voronoi Diagrams of Lines in Space Under Polyhedral Convex Distance Functions (2009) (0)
Implementation and Experimentation with Motion Planning Algorithms (1991) (0)
On the Bivariate Function Minimization Problem And Its Applications to Motion Planning (1987) (0)
Arrangements of surfaces: Evolution of the basic theory (2008) (0)
Efficient algorithms for optimization problems involving semi-algebraic range searching (2021) (0)
Crossing numbers of graphs: Graph drawing and its applications (2008) (0)
point sets. In J. N. Srivastava, editor, A Survey of Combinatorial Theory, pages (1998) (0)
Motion Amidst Polygonal Obstacles * (2005) (0)
From Sam Loyd and László Fejes Tóth: The 15 puzzle and motion planning (2008) (0)
5. Conclusion and Open Problems Step 4.3 for Each Internal Node Build Tablem , 1 for Array M in M , Level of the Tree Number of Children per Node (0)
Arrangements of Curves and Surfaces in Computational Geometry (1996) (0)
On the combinatorial complexity of the space of hyperplane transversals (1990) (0)
Near-Linear Approximation Algorithms for Geometric Hitting Sets (2011) (0)
Geometric coloring problems: Sphere packings and frequency allocation (2008) (0)
Tight bounds on a problem of lines and intersections (1991) (0)
Counting and Cutting Rich Lenses in Arrangements of Circles (2022) (0)
CS-1996-19 E cient Algorithms for GeometricOptimizationPankaj (2007) (0)
Generalizations of the Szemer\'edi-Trotter Theorem (2014) (0)
An Eecient Multi-dimensional Searching Technique and Its Applications an Eecient Multi-dimensional Searching Technique and Its Applications (2007) (0)
C G ] 1 2 O ct 2 01 4 ε-Nets for Halfspaces Revisited ∗ (2014) (0)
Extremal combinatorics: Repeated patterns and pattern recognition (2008) (0)
Lines in space: From ray shooting to geometric transversals (2008) (0)
The Elekes–Szabó Theorem in four dimensions (2018) (0)
Eecient Motion Planning for an L-shaped Object (1997) (0)
Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions (2015) (0)
A Nearly Quadratic Bound for k-SUM , and Point-Location in Hyperplane Arrangements , in the Linear Decision Tree Model ∗ (2017) (0)
On the Complexity of the k-Level in Arrangements of Pseudoplanes (2019) (0)
Generalizations of the Szemerédi–Trotter Theorem (2014) (0)
Improved Bounds for Incidences and Complexity of Many Faces in Arrangements of Circles and of Polynomial Arcs * (2000) (0)
Incidences Between Points and Lines in R4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb {R}}^4$$\end{documen (2016) (0)
Optimized-motion planning - theory and implementation by Cherif Ahrikencheikh and Ali Seireg : John Wiley & Sons Inc., Chichester (1994) 366 pp, ISBN 0-471-01903-8 (1997) (0)
4.3 a Data Structuring Approach (1994) (0)
The Algebraic Revolution in Combinatorial and Computational Geometry: State of the Art (Invited Talk) (2017) (0)
A strange sorting method inspired by formal differentiation (1981) (0)
Incidences Between Points and Lines on Two- and Three-Dimensional Varieties (2017) (0)
A Nearly Quadratic Bound for Point-Location in Hyperplane Arrangements, in the Linear Decision Tree Model (2018) (0)
LOWER BOUNDS FOR GEOMETRICAL AND PHYSICALPROBLEMSJ URGEN SELLEN (1996) (0)
Numerical Productivity Measures (0)
Optical Algorithms in Geometry (1993) (0)
Stable Delaunay Graphs (2015) (0)
On Triple Intersections of Three Families of Unit Circles (2015) (0)
Algebraic Techniques in Geometry: The 10th Anniversary (2018) (0)
Time and space efficient collinearity indexing (2022) (0)
Davenport-Schinzel sequences: The inverse Ackermann function in geometry (2008) (0)
Reaching a Goal with DirectionalUncertaintyMark (1994) (0)
Duality-based approximation algorithms for maximum depth (2020) (0)
SERIE B INFORMATIK A Subexponential Bound for Linear Programming (2009) (0)
The Maximum-Level Vertex in an Arrangement of Lines (2020) (0)
Line Transversals of Convex Polyhedra in $\reals^3$ (2008) (0)
Testing Transmission Graphs for Acyclicity ∗ (2019) (0)
Geometrically Aware Communication in Random Wireless Networks Reconsidered (2004) (0)
Jack Schwartz and Robotics: The Roaring Eighties (2013) (0)
Improved Algebraic Degeneracy Testing (2022) (0)
28 Arrangements (2016) (0)
Partial-Matching RMS Distance Under Translation: Combinatorics and Algorithms (2017) (0)
Complexity of Many Cells and Sum of Squares of Cell Complexities in Hyperplane Arrangements Too long ∗ (2007) (0)
Sek and S. Suri. Farthest Neighbors, Maximum Spanning Trees and Related Problems In (0)
Lower Bounds for Constant Depth Circuits for Preex Problems, in Proc. of 10th International 5. Conclusion and Open Problems (1992) (0)
Generalizations of the Szemerédi–Trotter Theorem (2016) (0)
k Directional Assembly Sequences � (2009) (0)
On the union of kapa-round objects. (2004) (0)
Depth contours in arrangements of halfplanes (2016) (0)
On the number of views of translates of a cube and related problems (2004) (0)
A note on the limitations of the Elekes-Sharir framework (2013) (0)
On Incidences Between Points and Hyperplanes ∗ (2005) (0)
Decomposing Arrangements of Hyperplanes: VC-Dimension, Combinatorial Dimension, and Point Location (2019) (0)
AD-- A 257 926 Implementation and Experimentation with Motion Planning Algorithms (0)
Ja n 20 10 Relative ( p , ε )-Approximations in Geometry ∗ (2010) (0)

This paper list is powered by the following services:

Other Resources About Micha Sharir

en.wikipedia.org

What Schools Are Affiliated With Micha Sharir?

Micha Sharir is affiliated with the following schools:

Image Attributions

Image Source for Micha Sharir