Micha Sharir

According to our database, Micha Sharir authored at least 482 papers between 1979 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Decomposing the Complement of the Union of Cubes and Boxes in Three Dimensions.

Pankaj K. Agarwal, Micha Sharir, Alex Steiger

Discret. Comput. Geom., September, 2024

On reverse shortest paths in geometric proximity graphs.

Pankaj K. Agarwal, Matthew J. Katz, Micha Sharir

Comput. Geom., February, 2024

Near-Optimal Min-Sum Motion Planning for Two Square Robots in a Polygonal Environment.

Pankaj K. Agarwal, Dan Halperin, Micha Sharir, Alex Steiger

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Vertical Decomposition in 3D and 4D with Applications to Line Nearest-Neighbor Searching in 3D.

Pankaj K. Agarwal, Esther Ezra, Micha Sharir

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Near-Linear Algorithms for Visibility Graphs over a 1.5-Dimensional Terrain.

Matthew J. Katz, Rachel Saban, Micha Sharir

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

Segment Proximity Graphs and Nearest Neighbor Queries Amid Disjoint Segments.

Pankaj K. Agarwal, Haim Kaplan, Matthew J. Katz, Micha Sharir

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

Lower Envelopes of Surface Patches in 3-Space.

Pankaj K. Agarwal, Esther Ezra, Micha Sharir

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

Semi-Algebraic Off-Line Range Searching and Biclique Partitions in the Plane.

Pankaj K. Agarwal, Esther Ezra, Micha Sharir

Proceedings of the 40th International Symposium on Computational Geometry, 2024

2023

Throwing a Sofa Through the Window.

Dan Halperin, Micha Sharir, Itay Yehuda

Discret. Comput. Geom., December, 2023

Space-Aware Reconfiguration.

Dan Halperin, Marc J. van Kreveld, Golan Miglioli-Levy, Micha Sharir

Discret. Comput. Geom., June, 2023

Bottleneck matching in the plane.

Matthew J. Katz, Micha Sharir

Comput. Geom., June, 2023

Time and space efficient collinearity indexing.

Boris Aronov, Esther Ezra, Micha Sharir, Guy Zigdon

Comput. Geom., 2023

Subquadratic algorithms for some 3Sum-hard geometric problems in the algebraic decision-tree model.

Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, Micha Sharir

Comput. Geom., 2023

The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs.

Haim Kaplan, Matthew J. Katz, Rachel Saban, Micha Sharir

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

Improved Algebraic Degeneracy Testing.

Jean Cardinal, Micha Sharir

Proceedings of the 39th International Symposium on Computational Geometry, 2023

2022

Counting and Cutting Rich Lenses in Arrangements of Circles.

Esther Ezra, Orit E. Raz, Micha Sharir, Joshua Zahl

SIAM J. Discret. Math., 2022

On Ray Shooting for Triangles in 3-Space and Related Problems.

Esther Ezra, Micha Sharir

SIAM J. Comput., 2022

Incidences between points and curves with almost two degrees of freedom.

Micha Sharir, Noam Solomon, Oleg Zlydenko

J. Comb. Theory A, 2022

The Maximum-Level Vertex in an Arrangement of Lines.

Dan Halperin, Sariel Har-Peled, Kurt Mehlhorn, Eunjin Oh, Micha Sharir

Discret. Comput. Geom., 2022

Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets: Collinearity Testing and Related Problems.

Boris Aronov, Esther Ezra, Micha Sharir

Discret. Comput. Geom., 2022

Intersection Searching amid Tetrahedra in Four Dimensions.

Esther Ezra, Micha Sharir

CoRR, 2022

Intersection Searching Amid Tetrahedra in 4-Space and Efficient Continuous Collision Detection.

Esther Ezra, Micha Sharir

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

Covering Points by Hyperplanes and Related Problems.

Zuzana Patáková, Micha Sharir

Proceedings of the 38th International Symposium on Computational Geometry, 2022

Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems.

Pankaj K. Agarwal, Boris Aronov, Esther Ezra, Matthew J. Katz, Micha Sharir

Proceedings of the 38th International Symposium on Computational Geometry, 2022

2021

Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic Õ(n^5/3) Time.

Pawel Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, Oren Weimann

SIAM J. Comput., 2021

On rich points and incidences with restricted sets of lines in 3-space.

Micha Sharir, Noam Solomon

J. Comput. Geom., 2021

On the complexity of the k-level in arrangements of pseudoplanes.

Micha Sharir, Chen Ziv

Discret. Math., 2021

Stabbing pairwise intersecting disks by five points.

Sariel Har-Peled, Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir, Max Willert

Discret. Math., 2021

Union of Hypercubes and 3D Minkowski Sums with Random Sizes.

Pankaj K. Agarwal, Haim Kaplan, Micha Sharir

Discret. Comput. Geom., 2021

Efficient algorithms for optimization problems involving distances in a point set.

Matthew J. Katz, Micha Sharir

CoRR, 2021

Decomposing the Complement of the Union of Cubes in Three Dimensions.

Pankaj K. Agarwal, Micha Sharir, Alex Steiger

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

On Rich Lenses in Planar Arrangements of Circles and Related Problems.

Esther Ezra, Orit E. Raz, Micha Sharir, Joshua Zahl

Proceedings of the 37th International Symposium on Computational Geometry, 2021

2020

Dynamic Planar Voronoi Diagrams for General Distance Functions and Their Algorithmic Applications.

Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir

Discret. Comput. Geom., 2020

Decomposing Arrangements of Hyperplanes: VC-Dimension, Combinatorial Dimension, and Point Location.

Esther Ezra, Sariel Har-Peled, Haim Kaplan, Micha Sharir

Discret. Comput. Geom., 2020

Eliminating Depth Cycles Among Triangles in Three Dimensions.

Boris Aronov, Edward Y. Miller, Micha Sharir

Discret. Comput. Geom., 2020

Incidences with curves in three dimensions.

Micha Sharir, Noam Solomon

CoRR, 2020

Duality-based approximation algorithms for depth queries and maximum depth.

Dror Aiger, Haim Kaplan, Micha Sharir

CoRR, 2020

On Radial Isotropic Position: Theory and Algorithms.

Shiri Artstein-Avidan, Haim Kaplan, Micha Sharir

CoRR, 2020

Output sensitive algorithms for approximate incidences and their applications.

Dror Aiger, Haim Kaplan, Micha Sharir

Comput. Geom., 2020

Incidences Between Points and Curves with Almost Two Degrees of Freedom.

Micha Sharir, Oleg Zlydenko

Proceedings of the 36th International Symposium on Computational Geometry, 2020

How to Find a Point in the Convex Hull Privately.

Haim Kaplan, Micha Sharir, Uri Stemmer

Proceedings of the 36th International Symposium on Computational Geometry, 2020

Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets.

Boris Aronov, Esther Ezra, Micha Sharir

Proceedings of the 36th International Symposium on Computational Geometry, 2020

2019

A Nearly Quadratic Bound for Point-Location in Hyperplane Arrangements, in the Linear Decision Tree Model.

Esther Ezra, Micha Sharir

Discret. Comput. Geom., 2019

Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points.

Haim Kaplan, Sasanka Roy, Micha Sharir

Comput. Geom., 2019

Triangles and Girth in Disk Graphs and Transmission Graphs.

Haim Kaplan, Katharina Klost, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

General Techniques for Approximate Incidences and Their Application to the Camera Posing Problem.

Dror Aiger, Haim Kaplan, Efi Kokiopoulou, Micha Sharir, Bernhard Zeisl

Proceedings of the 35th International Symposium on Computational Geometry, 2019

2018

Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier.

Omer Gold, Micha Sharir

ACM Trans. Algorithms, 2018

Distinct distances between a collinear set and an arbitrary set of points.

Ariel Bruner, Micha Sharir

Discret. Math., 2018

Homotheties and incidences.

Dror Aiger, Micha Sharir

Discret. Math., 2018

Incidences Between Points and Lines on Two- and Three-Dimensional Varieties.

Micha Sharir, Noam Solomon

Discret. Comput. Geom., 2018

Almost Tight Bounds for Eliminating Depth Cycles in Three Dimensions.

Boris Aronov, Micha Sharir

Discret. Comput. Geom., 2018

Distinct distances between points and lines.

Micha Sharir, Shakhar Smorodinsky, Claudiu Valculescu, Frank de Zeeuw

Comput. Geom., 2018

Partial-Matching RMS Distance Under Translation: Combinatorics and Algorithms.

Rinat Ben Avraham, Matthias Henze, Rafel Jaume, Balázs Keszegh, Orit E. Raz, Micha Sharir, Igor Tubis

Algorithmica, 2018

Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic <i>Õ</i>(<i>n</i>^5/3) Time.

Pawel Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, Oren Weimann

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Algebraic Techniques in Geometry: The 10th Anniversary.

Micha Sharir

Proceedings of the 2018 ACM on International Symposium on Symbolic and Algebraic Computation, 2018

Approximate Minimum-Weight Matching with Outliers Under Translation.

Pankaj K. Agarwal, Haim Kaplan, Geva Kipper, Wolfgang Mulzer, Günter Rote, Micha Sharir, Allen Xiao

Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

2017

Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices, and Their Applications.

Haim Kaplan, Shay Mozes, Yahav Nussbaum, Micha Sharir

ACM Trans. Algorithms, 2017

Computational Geometry Column 65.

Micha Sharir

SIGACT News, 2017

Cutting algebraic curves into pseudo-segments and applications.

Micha Sharir, Joshua Zahl

J. Comb. Theory A, 2017

Incidences Between Points and Lines in $${\mathbb {R}}^4$$.

Micha Sharir, Noam Solomon

Discret. Comput. Geom., 2017

On the number of unit-area triangles spanned by convex grids in the plane.

Orit E. Raz, Micha Sharir, Ilya D. Shkredov

Comput. Geom., 2017

The Number of Unit-Area Triangles in the Plane: Theme and Variation.

Orit E. Raz, Micha Sharir

Comb., 2017

Incidences with curves and surfaces in three dimensions, with applications to distinct and repeated distances.

Micha Sharir, Noam Solomon

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Dominance Product and High-Dimensional Closest Pair under L_infty.

Omer Gold, Micha Sharir

Proceedings of the 28th International Symposium on Algorithms and Computation, 2017

Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy.

Omer Gold, Micha Sharir

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Approximate Nearest Neighbor Search Amid Higher-Dimensional Flats.

Pankaj K. Agarwal, Natan Rubin, Micha Sharir

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

The Algebraic Revolution in Combinatorial and Computational Geometry: State of the Art (Invited Talk).

Micha Sharir

Proceedings of the 33rd International Symposium on Computational Geometry, 2017

A Nearly Quadratic Bound for the Decision Tree Complexity of k-SUM.

Esther Ezra, Micha Sharir

Proceedings of the 33rd International Symposium on Computational Geometry, 2017

2016

Generalizations of the Szemerédi-Trotter Theorem.

Saarik Kalia, Micha Sharir, Noam Solomon, Ben Yang

Discret. Comput. Geom., 2016

Distinct Distances from Three Points.

Micha Sharir, József Solymosi

Comb. Probab. Comput., 2016

The Elekes-Szabó Theorem in four dimensions.

Orit E. Raz, Micha Sharir, Frank de Zeeuw

CoRR, 2016

Approximating the $k$-Level in Three-Dimensional Plane Arrangements.

Sariel Har-Peled, Haim Kaplan, Micha Sharir

CoRR, 2016

Dynamic Time Warping: Breaking the Quadratic Barrier.

Omer Gold, Micha Sharir

CoRR, 2016

Dominance Products and Faster Algorithms for High-Dimensional Closest Pair under L_∞.

Omer Gold, Micha Sharir

CoRR, 2016

The Decision Tree Complexity for k-SUM is at most Nearly Quadratic.

Esther Ezra, Micha Sharir

CoRR, 2016

Incidences with Curves in ℝ^d.

Micha Sharir, Adam Sheffer, Noam Solomon

Electron. J. Comb., 2016

Approximating the <i>k</i>-Level in Three-Dimensional Plane Arrangements.

Sariel Har-Peled, Haim Kaplan, Micha Sharir

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection.

Rinat Ben Avraham, Omrit Filtser, Haim Kaplan, Matthew J. Katz, Micha Sharir

ACM Trans. Algorithms, 2015

Finding the largest disk containing a query point in logarithmic time with linear storage.

Tal Kaminker, Micha Sharir

J. Comput. Geom., 2015

Sets with few distinct distances do not have heavy lines.

Orit E. Raz, Oliver Roche-Newton, Micha Sharir

Discret. Math., 2015

On Triple Intersections of Three Families of Unit Circles.

Orit E. Raz, Micha Sharir, József Solymosi

Discret. Comput. Geom., 2015

Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions.

Pankaj K. Agarwal, Haim Kaplan, Natan Rubin, Micha Sharir

Discret. Comput. Geom., 2015

Stable Delaunay Graphs.

Pankaj K. Agarwal, Jie Gao, Leonidas J. Guibas, Haim Kaplan, Natan Rubin, Micha Sharir

Discret. Comput. Geom., 2015

Improved Bounds for Incidences Between Points and Circles.

Micha Sharir, Adam Sheffer, Joshua Zahl

Comb. Probab. Comput., 2015

Delaunay Triangulations of Degenerate Point Sets.

Michael Khanimov, Micha Sharir

CoRR, 2015

A faster algorithm for the discrete Fréchet distance under translation.

Rinat Ben Avraham, Haim Kaplan, Micha Sharir

CoRR, 2015

Incidences between Points and Lines in R^4.

Micha Sharir, Noam Solomon

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Incidences with Curves in ℝ d.

Micha Sharir, Adam Sheffer, Noam Solomon

Proceedings of the Algorithms - ESA 2015, 2015

Incidences between Points and Lines in Three Dimensions.

Micha Sharir, Noam Solomon

Proceedings of the 31st International Symposium on Computational Geometry, 2015

Polynomials Vanishing on Cartesian Products: The Elekes-Szabó Theorem Revisited.

Orit E. Raz, Micha Sharir, Frank de Zeeuw

Proceedings of the 31st International Symposium on Computational Geometry, 2015

The Number of Unit-Area Triangles in the Plane: Theme and Variations.

Orit E. Raz, Micha Sharir

Proceedings of the 31st International Symposium on Computational Geometry, 2015

2014

Improved Bounds for the Union of Locally Fat Objects in the Plane.

Boris Aronov, Mark de Berg, Esther Ezra, Micha Sharir

SIAM J. Comput., 2014

Reporting Neighbors in High-Dimensional Euclidean Space.

Dror Aiger, Haim Kaplan, Micha Sharir

SIAM J. Comput., 2014

Computing the Discrete Fréchet Distance in Subquadratic Time.

Pankaj K. Agarwal, Rinat Ben Avraham, Haim Kaplan, Micha Sharir

SIAM J. Comput., 2014

A note on distinct distances in rectangular lattices.

Javier Cilleruelo, Micha Sharir, Adam Sheffer

Discret. Math., 2014

Union of Random Minkowski Sums and Network Vulnerability Analysis.

Pankaj K. Agarwal, Sariel Har-Peled, Haim Kaplan, Micha Sharir

Discret. Comput. Geom., 2014

Epsilon-Nets for Halfspaces Revisited.

Sariel Har-Peled, Haim Kaplan, Micha Sharir, Shakhar Smorodinsky

CoRR, 2014

Partial-Matching and Hausdorff RMS Distance Under Translation: Combinatorics and Algorithms.

Rinat Ben Avraham, Matthias Henze, Rafel Jaume, Balázs Keszegh, Orit E. Raz, Micha Sharir, Igor Tubis

CoRR, 2014

Minimum Partial-Matching and Hausdorff RMS-Distance under Translation: Combinatorics and Algorithms.

Rinat Ben Avraham, Matthias Henze, Rafel Jaume, Balázs Keszegh, Orit E. Raz, Micha Sharir, Igor Tubis

Proceedings of the Algorithms - ESA 2014, 2014

Incidences between points and lines in R4: Extended Abstract.

Micha Sharir, Noam Solomon

Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

Polynomials vanishing on grids: The Elekes-Rónyai problem revisited.

Orit E. Raz, Micha Sharir, József Solymosi

Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

The Discrete Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection.

Rinat Ben Avraham, Omrit Filtser, Haim Kaplan, Matthew J. Katz, Micha Sharir

Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013

On Range Searching with Semialgebraic Sets. II.

Pankaj K. Agarwal, Jirí Matousek, Micha Sharir

SIAM J. Comput., 2013

Counting plane graphs: Perfect matchings, spanning cycles, and Kasteleyn's technique.

Micha Sharir, Adam Sheffer, Emo Welzl

J. Comb. Theory A, 2013

Distinct distances on two lines.

Micha Sharir, Adam Sheffer, József Solymosi

J. Comb. Theory A, 2013

Finding the largest Empty Disk containing a Query Point.

Haim Kaplan, Micha Sharir

Int. J. Comput. Geom. Appl., 2013

Counting Plane Graphs: Cross-Graph Charging Schemes.

Micha Sharir, Adam Sheffer

Comb. Probab. Comput., 2013

Distinct distances on two lines

Micha Sharir, Adam Sheffer

CoRR, 2013

Output-Sensitive Tools for Range Searching in Higher Dimensions.

Micha Sharir, Shai Zaban

CoRR, 2013

On lattices, distinct distances, and the Elekes-Sharir framework.

Javier Cilleruelo, Micha Sharir, Adam Sheffer

CoRR, 2013

The Discrete Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection Techniques.

Rinat Ben Avraham, Omrit Filtser, Haim Kaplan, Matthew J. Katz, Micha Sharir

CoRR, 2013

The 2-center problem in three dimensions.

Pankaj K. Agarwal, Rinat Ben Avraham, Micha Sharir

Comput. Geom., 2013

On the Union Complexity of Diametral Disks.

Boris Aronov, Muriel Dulieu, Rom Pinchasi, Micha Sharir

Electron. J. Comb., 2013

Reporting neighbors in high-dimensional Euclidean spaces.

Dror Aiger, Haim Kaplan, Micha Sharir

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Union of random minkowski sums and network vulnerability analysis.

Pankaj K. Agarwal, Haim Kaplan, Micha Sharir

Proceedings of the Symposium on Computational Geometry 2013, 2013

2012

Improved Bounds for Geometric Permutations.

Natan Rubin, Haim Kaplan, Micha Sharir

SIAM J. Comput., 2012

Simple Proofs of Classical Theorems in Discrete Geometry via the Guth-Katz Polynomial Partitioning Technique.

Haim Kaplan, Jirí Matousek, Micha Sharir

Discret. Comput. Geom., 2012

Unit Distances in Three Dimensions.

Haim Kaplan, Jirí Matousek, Zuzana Safernová, Micha Sharir

Comb. Probab. Comput., 2012

Incidences between points and non-coplanar circles

Micha Sharir, Adam Sheffer, Joshua Zahl

CoRR, 2012

Near-Linear Approximation Algorithms for Geometric Hitting Sets.

Pankaj K. Agarwal, Esther Ezra, Micha Sharir

Algorithmica, 2012

Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications.

Haim Kaplan, Shay Mozes, Yahav Nussbaum, Micha Sharir

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Finding the maximal empty disk containing a query point.

Haim Kaplan, Micha Sharir

Proceedings of the 28th ACM Symposium on Computational Geometry, 2012

2011

Semialgebraic Range Reporting and Emptiness Searching with Applications.

Micha Sharir, Hayim Shaul

SIAM J. Comput., 2011

Optimal Cover of Points by Disks in a Simple Polygon.

Haim Kaplan, Matthew J. Katz, Gila Morgenstern, Micha Sharir

SIAM J. Comput., 2011

On degrees in random triangulations of point sets.

Micha Sharir, Adam Sheffer, Emo Welzl

J. Comb. Theory A, 2011

On lines, joints, and incidences in three dimensions.

György Elekes, Haim Kaplan, Micha Sharir

J. Comb. Theory A, 2011

The Overlay of Minimization Diagrams in a Randomized Incremental Construction.

Haim Kaplan, Edgar Ramos, Micha Sharir

Discret. Comput. Geom., 2011

Range Minima Queries with Respect to a Random Permutation, and Approximate Range Counting.

Haim Kaplan, Edgar Ramos, Micha Sharir

Discret. Comput. Geom., 2011

Relative (<i>p</i>, <i>ε</i>)-Approximations in Geometry.

Sariel Har-Peled, Micha Sharir

Discret. Comput. Geom., 2011

An Improved Bound for <i>k</i>-Sets in Four Dimensions.

Micha Sharir

Comb. Probab. Comput., 2011

Incidences in Three Dimensions and Distinct Distances in the Plane.

György Elekes, Micha Sharir

Comb. Probab. Comput., 2011

Non-Degenerate Spheres in Three Dimensions.

Roel Apfelbaum, Micha Sharir

Comb. Probab. Comput., 2011

Finding the Maximal Empty Rectangle Containing a Query Point

Haim Kaplan, Micha Sharir

CoRR, 2011

A kinetic triangulation scheme for moving points in the plane.

Haim Kaplan, Natan Rubin, Micha Sharir

Comput. Geom., 2011

Counting Triangulations of Planar Point Sets.

Micha Sharir, Adam Sheffer

Electron. J. Comb., 2011

Counting Plane Graphs: Flippability and Its Applications.

Michael Hoffmann, Micha Sharir, Adam Sheffer, Csaba D. Tóth, Emo Welzl

Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Improved Bound for the Union of Fat Triangles.

Esther Ezra, Boris Aronov, Micha Sharir

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010

Constructing Two-Dimensional Voronoi Diagrams via Divide-and-Conquer of Envelopes in Space.

Ophir Setter, Micha Sharir, Dan Halperin

Trans. Comput. Sci., 2010

Hausdorff distance under translation for points and balls.

Pankaj K. Agarwal, Sariel Har-Peled, Micha Sharir, Yusu Wang

ACM Trans. Algorithms, 2010

Line Transversals of Convex Polyhedra in R³.

Haim Kaplan, Natan Rubin, Micha Sharir

SIAM J. Comput., 2010

Approximate Halfspace Range Counting.

Boris Aronov, Micha Sharir

SIAM J. Comput., 2010

Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes.

Boris Aronov, Esther Ezra, Micha Sharir

SIAM J. Comput., 2010

On Lines and Joints.

Haim Kaplan, Micha Sharir, Eugenii Shustin

Discret. Comput. Geom., 2010

An Improved Bound on the Number of Unit Area Triangles.

Roel Apfelbaum, Micha Sharir

Discret. Comput. Geom., 2010

Guarding a Terrain by Two Watchtowers.

Pankaj K. Agarwal, Sergey Bereg, Ovidiu Daescu, Haim Kaplan, Simeon C. Ntafos, Micha Sharir, Binhai Zhu

Algorithmica, 2010

Kinetic stable Delaunay graphs.

Pankaj K. Agarwal, Jie Gao, Leonidas J. Guibas, Haim Kaplan, Vladlen Koltun, Natan Rubin, Micha Sharir

Proceedings of the 26th ACM Symposium on Computational Geometry, 2010

Algorithm Derivation by Transformations (reprint).

Micha Sharir

General Books, ISBN: 978-1-154-60684-3, 2010

Combinatorial Complexity Bounds for Arrangements of Curves and Surfaces (reprint).

Kenneth L. Clarkson, Micha Sharir

General Books, ISBN: 978-1-153-46242-6, 2010

2009

Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles.

Ke Chen, Haim Kaplan, Micha Sharir

ACM Trans. Algorithms, 2009

Eppstein's bound on intersecting triangles revisited.

Gabriel Nivasch, Micha Sharir

J. Comb. Theory A, 2009

Extremal problems on triangle areas in two and three dimensions.

Adrian Dumitrescu, Micha Sharir, Csaba D. Tóth

J. Comb. Theory A, 2009

On the union of fat tetrahedra in three dimensions.

Esther Ezra, Micha Sharir

J. ACM, 2009

On Overlays and Minimization Diagrams.

Vladlen Koltun, Micha Sharir

Discret. Comput. Geom., 2009

On Regular Vertices of the Union of Planar Convex Objects.

Esther Ezra, János Pach, Micha Sharir

Discret. Comput. Geom., 2009

Counting Triangulations of Planar Point Sets

Micha Sharir, Adam Sheffer, Emo Welzl

CoRR, 2009

Relative (p,epsilon)-Approximations in Geometry

Sariel Har-Peled, Micha Sharir

CoRR, 2009

Semi-algebraic Range Reporting and Emptiness Searching with Applications

Micha Sharir, Hayim Shaul

CoRR, 2009

Linear Data Structures for Fast Ray-Shooting amidst Convex Polyhedra.

Haim Kaplan, Natan Rubin, Micha Sharir

Algorithmica, 2009

Small-size epsilon-nets for axis-parallel rectangles and boxes.

Boris Aronov, Esther Ezra, Micha Sharir

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Line transversals of convex polyhedra in <i>R</i>³.

Haim Kaplan, Natan Rubin, Micha Sharir

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008

Algorithms for center and Tverberg points.

Pankaj K. Agarwal, Micha Sharir, Emo Welzl

ACM Trans. Algorithms, 2008

Kinetic and dynamic data structures for closest pair and all nearest neighbors.

Pankaj K. Agarwal, Haim Kaplan, Micha Sharir

ACM Trans. Algorithms, 2008

Efficient Colored Orthogonal Range Counting.

Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin

SIAM J. Comput., 2008

On planar intersection graphs with forbidden subgraphs.

János Pach, Micha Sharir

J. Graph Theory, 2008

Weak ε-nets and interval chains.

Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky

J. ACM, 2008

An Optimal-Time Algorithm for Shortest Paths on a Convex Polytope in Three Dimensions.

Yevgeny Schreiber, Micha Sharir

Discret. Comput. Geom., 2008

Efficient Algorithms for Maximum Regression Depth.

Marc J. van Kreveld, Joseph S. B. Mitchell, Peter J. Rousseeuw, Micha Sharir, Jack Snoeyink, Bettina Speckmann

Discret. Comput. Geom., 2008

Computing the Detour and Spanning Ratio of Paths, Trees, and Cycles in 2D and 3D.

Pankaj K. Agarwal, Rolf Klein, Christian Knauer, Stefan Langerman, Pat Morin, Micha Sharir, Michael A. Soss

Discret. Comput. Geom., 2008

On the performance of the ICP algorithm.

Esther Ezra, Micha Sharir, Alon Efrat

Comput. Geom., 2008

Stabbing Convex Polygons with a Segment or a Polygon.

Pankaj K. Agarwal, Danny Z. Chen, Shashidhara K. Ganjugunte, Ewa Misiolek, Micha Sharir, Kai Tang

Proceedings of the Algorithms, 2008

The complexity of the outer face in arrangements of random segments.

Noga Alon, Dan Halperin, Oren Nechushtan, Micha Sharir

Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

2007

Large Complete Bipartite Subgraphs In Incidence Graphs Of Points And Hyperplanes.

Roel Apfelbaum, Micha Sharir

SIAM J. Discret. Math., 2007

Online Conflict-Free Coloring for Intervals.

Ke Chen, Amos Fiat, Haim Kaplan, Meital Levy, Jirí Matousek, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, Emo Welzl

SIAM J. Comput., 2007

Solution of Scott's Problem on the Number of Directions Determined by a Point Set in 3-Space.

János Pach, Rom Pinchasi, Micha Sharir

Discret. Comput. Geom., 2007

A Single Cell in an Arrangement of Convex Polyhedra in \Bbb <i>R</i>³.

Esther Ezra, Micha Sharir

Discret. Comput. Geom., 2007

Kinetic and dynamic data structures for convex hulls and upper envelopes.

Giora Alexandron, Haim Kaplan, Micha Sharir

Comput. Geom., 2007

Counting colors in boxes.

Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions.

Esther Ezra, Micha Sharir

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Arrangements in Geometry: Recent Advances and Challenges.

Micha Sharir

Proceedings of the Algorithms, 2007

Bi-criteria linear-time approximations for generalized k-mean/median/center.

Dan Feldman, Amos Fiat, Micha Sharir, Danny Segev

Proceedings of the 23rd ACM Symposium on Computational Geometry, 2007

On regular vertices on the union of planar objects.

Esther Ezra, János Pach, Micha Sharir

Proceedings of the 23rd ACM Symposium on Computational Geometry, 2007

On approximate halfspace range counting and relative epsilon-approximations.

Boris Aronov, Sariel Har-Peled, Micha Sharir

Proceedings of the 23rd ACM Symposium on Computational Geometry, 2007

Computing the volume of the union of cubes.

Pankaj K. Agarwal, Haim Kaplan, Micha Sharir

Proceedings of the 23rd ACM Symposium on Computational Geometry, 2007

Similar simplices in a d-dimensional point set.

Pankaj K. Agarwal, Roel Apfelbaum, George B. Purdy, Micha Sharir

Proceedings of the 23rd ACM Symposium on Computational Geometry, 2007

2006

On the Number of Crossing-Free Matchings, Cycles, and Partitions.

Micha Sharir, Emo Welzl

SIAM J. Comput., 2006

Computing Maximally Separated Sets in the Plane.

Pankaj K. Agarwal, Mark H. Overmars, Micha Sharir

SIAM J. Comput., 2006

On empty convex polygons in a planar point set.

Rom Pinchasi, Rados Radoicic, Micha Sharir

J. Comb. Theory A, 2006

Minkowski Sums of Monotone and General Simple Polygons.

Eduard Oks, Micha Sharir

Discret. Comput. Geom., 2006

k-Sets in Four Dimensions.

Jirí Matousek, Micha Sharir, Shakhar Smorodinsky, Uli Wagner

Discret. Comput. Geom., 2006

On the Union of kappa-Round Objects in Three and Four Dimensions.

Boris Aronov, Alon Efrat, Vladlen Koltun, Micha Sharir

Discret. Comput. Geom., 2006

Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting.

Haim Kaplan, Micha Sharir

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Computing a Center-Transversal Line.

Pankaj K. Agarwal, Sergio Cabello, Joan Antoni Sellarès, Micha Sharir

Proceedings of the FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 2006

Coresets forWeighted Facilities and Their Applications.

Dan Feldman, Amos Fiat, Micha Sharir

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Random triangulations of planar point sets.

Micha Sharir, Emo Welzl

Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

Colored intersection searching via sparse rectangular matrix multiplication.

Haim Kaplan, Micha Sharir, Elad Verbin

Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

On the ICP algorithm.

Esther Ezra, Micha Sharir, Alon Efrat

Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

2005

Repeated Angles in Three and Four Dimensions.

Roel Apfelbaum, Micha Sharir

SIAM J. Discret. Math., 2005

Top-Down Analysis of Path Compression.

Raimund Seidel, Micha Sharir

SIAM J. Comput., 2005

Curve-Sensitive Cuttings.

Vladlen Koltun, Micha Sharir

SIAM J. Comput., 2005

Output-Sensitive Construction of the Union of Triangles.

Esther Ezra, Micha Sharir

SIAM J. Comput., 2005

Pseudo-Line Arrangements: Duality, Algorithms, and Applications.

Pankaj K. Agarwal, Micha Sharir

SIAM J. Comput., 2005

Crossing patterns of semi-algebraic sets.

Noga Alon, János Pach, Rom Pinchasi, Rados Radoicic, Micha Sharir

J. Comb. Theory A, 2005

Topological Graphs with No Large Grids.

János Pach, Rom Pinchasi, Micha Sharir, Géza Tóth

Graphs Comb., 2005

An Improved Bound for Joints in Arrangements of Lines in Space.

Sharona Feldman, Micha Sharir

Discret. Comput. Geom., 2005

Cutting Triangular Cycles of Lines in Space.

Boris Aronov, Vladlen Koltun, Micha Sharir

Discret. Comput. Geom., 2005

Incidences between Points and Circles in Three and Higher Dimensions.

Boris Aronov, Vladlen Koltun, Micha Sharir

Discret. Comput. Geom., 2005

Lines Avoiding Unit Balls in Three Dimensions.

Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun, Micha Sharir

Discret. Comput. Geom., 2005

Ray shooting and stone throwing with near-linear storage.

Micha Sharir, Hayim Shaul

Comput. Geom., 2005

Counting and representing intersections among triangles in three dimensions.

Esther Ezra, Micha Sharir

Comput. Geom., 2005

On Graphs That Do Not Contain The Cube And Related Problems.

Rom Pinchasi, Micha Sharir

Comb., 2005

Ray shooting amid balls, farthest point from a line, and range emptiness searching.

Micha Sharir, Hayim Shaul

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

The interface between computational and combinatorial geometry.

Micha Sharir

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Online conflict-free coloring for intervals.

Amos Fiat, Meital Levy, Jirí Matousek, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, Emo Welzl

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004

Algorithmic motion planning.

Micha Sharir

Proceedings of the Handbook of Discrete and Computational Geometry, Second Edition., 2004

The Simplex Algorithm in Dimension Three.

Volker Kaibel, Rafael Mechtel, Micha Sharir, Günter M. Ziegler

SIAM J. Comput., 2004

On the number of directions determined by a three-dimensional points set.

János Pach, Rom Pinchasi, Micha Sharir

J. Comb. Theory A, 2004

Lenses in arrangements of pseudo-circles and their applications.

Pankaj K. Agarwal, Eran Nevo, János Pach, Rom Pinchasi, Micha Sharir, Shakhar Smorodinsky

J. ACM, 2004

Polyhedral Voronoi Diagrams of Polyhedra in Three Dimensions.

Vladlen Koltun, Micha Sharir

Discret. Comput. Geom., 2004

Binary Space Partitions for Axis-Parallel Segments, Rectangles, and Hyperrectangles.

Adrian Dumitrescu, Joseph S. B. Mitchell, Micha Sharir

Discret. Comput. Geom., 2004

Cell Complexities in Hyperplane Arrangements.

Boris Aronov, Micha Sharir

Discret. Comput. Geom., 2004

Selecting Points that are Heavily Covered by Pseudo-Circles, Spheres or Rectangles.

Shakhar Smorodinsky, Micha Sharir

Comb. Probab. Comput., 2004

Point-Line Incidences in Space.

Micha Sharir, Emo Welzl

Comb. Probab. Comput., 2004

Distinct Distances in Three and Higher Dimensions.

Boris Aronov, János Pach, Micha Sharir, Gábor Tardos

Comb. Probab. Comput., 2004

Speeding up the incremental construction of the union of geometric objects in practice.

Eti Ezra, Dan Halperin, Micha Sharir

Comput. Geom., 2004

On the number of views of translates of a cube and related problems.

Boris Aronov, Robert Schiffenbauer, Micha Sharir

Comput. Geom., 2004

Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks.

Pankaj K. Agarwal, Mark H. Overmars, Micha Sharir

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Geometrically aware communication in random wireless networks.

Gady Kozma, Zvi Lotker, Micha Sharir, Gideon Stupp

Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

New results on shortest paths in three dimensions.

Joseph S. B. Mitchell, Micha Sharir

Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

On the union of kapa-round objects.

Boris Aronov, Alon Efrat, Vladlen Koltun, Micha Sharir

Proceedings of the 20th ACM Symposium on Computational Geometry, 2004

2003

The Partition Technique for Overlays of Envelopes.

Vladlen Koltun, Micha Sharir

SIAM J. Comput., 2003

3-Dimensional Euclidean Voronoi Diagrams of Lines with a Fixed Number of Orientations.

Vladlen Koltun, Micha Sharir

SIAM J. Comput., 2003

The Minkowski sum of a simple polygon and a segment.

Gennady Pustylnik, Micha Sharir

Inf. Process. Lett., 2003

On neighbors in geometric permutations.

Micha Sharir, Shakhar Smorodinsky

Discret. Math., 2003

The Union of Congruent Cubes in Three Dimensions.

János Pach, Ido Safruti, Micha Sharir

Discret. Comput. Geom., 2003

The Clarkson-Shor Technique Revisited And Extended.

Micha Sharir

Comb. Probab. Comput., 2003

Extremal Configurations and Levels in Pseudoline Arrangements.

Micha Sharir, Shakhar Smorodinsky

Proceedings of the Algorithms and Data Structures, 8th International Workshop, 2003

Ray Shooting and Stone Throwing.

Micha Sharir, Hayim Shaul

Proceedings of the Algorithms, 2003

A tight bound for the number of different directions in three dimensions.

János Pach, Rom Pinchasi, Micha Sharir

Proceedings of the 19th ACM Symposium on Computational Geometry, 2003

2002

The 2-Center Problem with Obstacles.

Dan Halperin, Micha Sharir, Kenneth Y. Goldberg

J. Algorithms, 2002

Cutting Circles into Pseudo-Segments and Improved Bounds for Incidences% and Complexity of Many Faces.

Boris Aronov, Micha Sharir

Discret. Comput. Geom., 2002

The Number of Congruent Simplices in a Point Set.

Pankaj K. Agarwal, Micha Sharir

Discret. Comput. Geom., 2002

Reporting intersecting pairs of convex polytopes in two and three dimensions.

Pankaj K. Agarwal, Mark de Berg, Sariel Har-Peled, Mark H. Overmars, Micha Sharir, Jan Vahrenhold

Comput. Geom., 2002

On the overlay of envelopes in four dimensions.

Vladlen Koltun, Micha Sharir

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Translating a Planar Object to Maximize Point Containment.

Pankaj K. Agarwal, Torben Hagerup, Rahul Ray, Micha Sharir, Michiel H. M. Smid, Emo Welzl

Proceedings of the Algorithms, 2002

Lenses in arrangements of pseudo-circles and their applications.

Eran Nevo, János Pach, Rom Pinchasi, Micha Sharir, Shakhar Smorodinsky

Proceedings of the 18th Annual Symposium on Computational Geometry, 2002

Three dimensional euclidean Voronoi diagrams of lines with a fixed number of orientations.

Vladlen Koltun, Micha Sharir

Proceedings of the 18th Annual Symposium on Computational Geometry, 2002

2001

Radial Points in the Plane.

János Pach, Micha Sharir

Eur. J. Comb., 2001

An Improved Bound for <i>k</i>-Sets in Three Dimensions.

Micha Sharir, Shakhar Smorodinsky, Gábor Tardos

Discret. Comput. Geom., 2001

Online Point Location in Planar Arrangements and Its Applications.

Sariel Har-Peled, Micha Sharir

Discret. Comput. Geom., 2001

On the Number of Regular Vertices of the Union of Jordan Regions.

Boris Aronov, Alon Efrat, Dan Halperin, Micha Sharir

Discret. Comput. Geom., 2001

On the Complexity of Arrangements of Circles in the Plane.

Noga Alon, Hagit Last, Rom Pinchasi, Micha Sharir

Discret. Comput. Geom., 2001

Exact and Approximation Algorithms for Minimum-Width Cylindrical Shells.

Pankaj K. Agarwal, Boris Aronov, Micha Sharir

Discret. Comput. Geom., 2001

Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions.

Pankaj K. Agarwal, Mark de Berg, Sariel Har-Peled, Mark H. Overmars, Micha Sharir, Jan Vahrenhold

Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001

On the Complexity of Many Faces in Arrangements of Circles.

Pankaj K. Agarwal, Boris Aronov, Micha Sharir

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Balanced lines, halving triangles, and the generalized lower bound theorem.

Micha Sharir, Emo Welzl

Proceedings of the Seventeenth Annual Symposium on Computational Geometry, 2001

On the number of congruent simplices in a point.

Pankaj K. Agarwal, Micha Sharir

Proceedings of the Seventeenth Annual Symposium on Computational Geometry, 2001

2000

Penetration Depth of Two Convex Polytopes in 3D.

Pankaj K. Agarwal, Leonidas J. Guibas, Sariel Har-Peled, Alexander Rabinovitch, Micha Sharir

Nord. J. Comput., 2000

Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls in Rd.

Shakhar Smorodinsky, Joseph S. B. Mitchell, Micha Sharir

Discret. Comput. Geom., 2000

On the Complexity of the Union of Fat Convex Objects in the Plane.

Alon Efrat, Micha Sharir

Discret. Comput. Geom., 2000

Pipes, Cigars, and Kreplach: the Union of Minkowski Sums in Three Dimensions.

Pankaj K. Agarwal, Micha Sharir

Discret. Comput. Geom., 2000

Approximation Algorithms for Minimum-Width Annuli and Shells.

Pankaj K. Agarwal, Boris Aronov, Sariel Har-Peled, Micha Sharir

Discret. Comput. Geom., 2000

Dynamic data structures for fat objects and their applications.

Alon Efrat, Matthew J. Katz, Frank Nielsen, Micha Sharir

Comput. Geom., 2000

Computing the Penetration Depth of Two Convex Polytopes in 3D.

Pankaj K. Agarwal, Leonidas J. Guibas, Sariel Har-Peled, Alexander Rabinovitch, Micha Sharir

Proceedings of the Algorithm Theory, 2000

An Improved Bound for k-Sets in Three Dimensions.

Micha Sharir, Shakhar Smorodinsky, Gábor Tardos

EuroCG, 2000

Arrangements and Their Applications.

Pankaj K. Agarwal, Micha Sharir

Proceedings of the Handbook of Computational Geometry, 2000

Davenport-Schinzel Sequences and Their Geometric Applications.

Pankaj K. Agarwal, Micha Sharir

Proceedings of the Handbook of Computational Geometry, 2000

1999

Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications.

Pankaj K. Agarwal, Alon Efrat, Micha Sharir

SIAM J. Comput., 1999

On the Boundary of the Union of Planar Convex Sets.

János Pach, Micha Sharir

Discret. Comput. Geom., 1999

Line Transversals of Balls and Smallest Enclosing Cylinders in Three Dimensions.

Pankaj K. Agarwal, Boris Aronov, Micha Sharir

Discret. Comput. Geom., 1999

Motion Planning for a Convex Polygon in a Polygonal Environment.

Pankaj K. Agarwal, Boris Aronov, Micha Sharir

Discret. Comput. Geom., 1999

Partial surface matching by using directed footprints.

Gill Barequet, Micha Sharir

Comput. Geom., 1999

Motion Planning of a Ball Amid Segments in Three Dimensions.

Pankaj K. Agarwal, Micha Sharir

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Recent Developments in the Theory of Arrangements of Surfaces.

Micha Sharir

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1999

Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls inR^d.

Shakhar Smorodinsky, Joseph S. B. Mitchell, Micha Sharir

Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

Approximation and Exact Algorithms for Minimum-Width Annuli and Shells.

Pankaj K. Agarwal, Boris Aronov, Sariel Har-Peled, Micha Sharir

Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

1998

Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions.

L. Paul Chew, Klara Kedem, Micha Sharir, Boaz Tagansky, Emo Welzl

J. Algorithms, 1998

Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions.

Jean-Daniel Boissonnat, Micha Sharir, Boaz Tagansky, Mariette Yvinec

Discret. Comput. Geom., 1998

The Discrete 2-Center Problem.

Pankaj K. Agarwal, Micha Sharir, Emo Welzl

Discret. Comput. Geom., 1998

Largest Placement of One Convex Polygon Inside Another.

Pankaj K. Agarwal, Nina Amenta, Micha Sharir

Discret. Comput. Geom., 1998

On Levels in Arrangements of Lines, Segments, Planes, and Triangles%.

Pankaj K. Agarwal, Boris Aronov, Timothy M. Chan, Micha Sharir

Discret. Comput. Geom., 1998

Efficient Algorithms for Geometric Optimization.

Pankaj K. Agarwal, Micha Sharir

ACM Comput. Surv., 1998

On the Number of Incidences Between Points and Curves.

János Pach, Micha Sharir

Comb. Probab. Comput., 1998

1997

Ray Shooting Amidst Spheres in Three Dimensions and Related Problems.

Shai Mohaban, Micha Sharir

SIAM J. Comput., 1997

An Expander-Based Approach to Geometric Optimization.

Matthew J. Katz, Micha Sharir

SIAM J. Comput., 1997

The Union of Convex Polyhedra in Three Dimensions.

Boris Aronov, Micha Sharir, Boaz Tagansky

SIAM J. Comput., 1997

On Translational Motion Planning of a Convex Polyhedron in 3-Space.

Boris Aronov, Micha Sharir

SIAM J. Comput., 1997

Computing Envelopes in Four Dimensions with Applications.

Pankaj K. Agarwal, Boris Aronov, Micha Sharir

SIAM J. Comput., 1997

Approximating shortest paths on a convex polytope in three dimensions.

Pankaj K. Agarwal, Sariel Har-Peled, Micha Sharir, Kasturi R. Varadarajan

J. ACM, 1997

A Near-Linear Algorithm for the Planar 2-Center Problem.

Micha Sharir

Discret. Comput. Geom., 1997

Vertical Decomposition of a Single Cell in a Three-Dimensional Arrangement of Surfaces.

Otfried Schwarzkopf, Micha Sharir

Discret. Comput. Geom., 1997

On Critical Orientations in the Kedem-Sharir Motion Planning Algorithm.

Klara Kedem, Micha Sharir, Sivan Toledo

Discret. Comput. Geom., 1997

The Common Exterior of Convex Polygons in the Plane.

Boris Aronov, Micha Sharir

Comput. Geom., 1997

Quasi-Planar Graphs Have a Linear Number of Edges.

Pankaj K. Agarwal, Boris Aronov, János Pach, Richard Pollack, Micha Sharir

Comb., 1997

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.

Micha Sharir

Comput. Aided Des., 1997

Line Traversals of Balls and Smallest Enclosing Cylinders in Three Dimensions.

Pankaj K. Agarwal, Boris Aronov, Micha Sharir

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

On the Complexity of the Union of Fat Objects in the Plane.

Alon Efrat, Micha Sharir

Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

On Levels in Arrangements of Lines, Segments, Planes, and Triangles.

Pankaj K. Agarwal, Boris Aronov, Micha Sharir

Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

1996

Ray Shooting amidst Convex Polyhedra and Polyhedral Terrains in Three Dimensions.

Pankaj K. Agarwal, Micha Sharir

SIAM J. Comput., 1996

Ray Shooting Amidst Convex Polygons in 2D.

Pankaj K. Agarwal, Micha Sharir

J. Algorithms, 1996

Excess in Arrangements of Segments.

Micha Sharir

Inf. Process. Lett., 1996

A Near-Quadratic Algorithm for Planning the Motion of a Polygon in a Polygonal Environment.

Dan Halperin, Micha Sharir

Discret. Comput. Geom., 1996

A Near-Linear Algorithm for the Planar Segment-Center Problem.

Alon Efrat, Micha Sharir

Discret. Comput. Geom., 1996

The Overlay of Lower Envelopes and Its Applications.

Pankaj K. Agarwal, Otfried Schwarzkopf, Micha Sharir

Discret. Comput. Geom., 1996

Efficient Randomized Algorithms for Some Geometric. Optimization Problems.

Pankaj K. Agarwal, Micha Sharir

Discret. Comput. Geom., 1996

Piecewise-Linear Interpolation between Polygonal Slices.

Gill Barequet, Micha Sharir

Comput. Vis. Image Underst., 1996

A Subexponential Bound for Linear Programming.

Jirí Matousek, Micha Sharir, Emo Welzl

Algorithmica, 1996

Lines in Space: Combinatorics and Algorithms.

Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Jorge Stolfi

Algorithmica, 1996

Efficient Generation of k-Directional Assembly Sequences.

Pankaj K. Agarwal, Mark de Berg, Dan Halperin, Micha Sharir

Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Arrangements of Curves and Surfaces in Computational Geometry.

Micha Sharir

Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, 1996

Rectilinear and Polygonal <i>p</i>-Piercing and <i>p</i>-Center Problems.

Micha Sharir, Emo Welzl

Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

Vertical Decomposition of a Single Cell in a Three-Dimensional Arrangement of Surfaces and Its Applications.

Otfried Schwarzkopf, Micha Sharir

Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

Approximating Shortest Paths on a Convex Polytope in Three Dimensions.

Sariel Har-Peled, Micha Sharir, Kasturi R. Varadarajan

Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

1995

Reaching a Goal with Directional Uncertainty.

Mark de Berg, Leonidas J. Guibas, Dan Halperin, Mark H. Overmars, Otfried Schwarzkopf, Micha Sharir, Monique Teillaud

Theor. Comput. Sci., 1995

Almost Tight Upper Bounds for the Single Cell and Zone Problems in Three Dimensions.

Dan Halperin, Micha Sharir

Discret. Comput. Geom., 1995

Vertical Decomposition of Arrangements of Hyperplanes in Four Dimensions.

Leonidas J. Guibas, Dan Halperin, Jirí Matousek, Micha Sharir

Discret. Comput. Geom., 1995

An Elementary Approach to Lower Bounds in Geometric Discrepancy.

Bernard Chazelle, Jirí Matousek, Micha Sharir

Discret. Comput. Geom., 1995

Improved Bounds on Weak epsilon-Nets for Convex Sets.

Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas J. Guibas, Micha Sharir, Emo Welzl

Discret. Comput. Geom., 1995

Computing Depth Orders for Fat Objects and Related Problems.

Pankaj K. Agarwal, Matthew J. Katz, Micha Sharir

Comput. Geom., 1995

Filling gaps in the boundary of a polyhedron.

Gill Barequet, Micha Sharir

Comput. Aided Geom. Des., 1995

Arrangements in Higher Dimensions: Voronoi Diagrams, Motion Planning, and Other Applications.

Micha Sharir

Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

The Overlay of Lower Envelopes in Three Dimensions and Its Applications.

Pankaj K. Agarwal, Otfried Schwarzkopf, Micha Sharir

Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

Algorithmic Techniques for Geometric Optimization.

Pankaj K. Agarwal, Micha Sharir

Proceedings of the Computer Science Today: Recent Trends and Developments, 1995

Davenport-Schinzel sequences and their geometric applications.

Micha Sharir, Pankaj K. Agarwal

Cambridge University Press, ISBN: 978-0-521-47025-4, 1995

1994

Fat Triangles Determine Linearly Many Holes.

Jirí Matousek, János Pach, Micha Sharir, Shmuel Sifrony, Emo Welzl

SIAM J. Comput., 1994

Selecting Heavily Covered Points.

Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, John Hershberger, Raimund Seidel, Micha Sharir

SIAM J. Comput., 1994

On Joints in Arrangements of Lines in Space and Related Problems.

Micha Sharir

J. Comb. Theory A, 1994

On the Sum of Squares of Cell Complexities in Hyperplane Arrangements.

Boris Aronov, Jirí Matousek, Micha Sharir

J. Comb. Theory A, 1994

Applications of Parametric Searching in Geometric Optimization.

Pankaj K. Agarwal, Micha Sharir, Sivan Toledo

J. Algorithms, 1994

Motion Planning in the Presence of Moving Obstacles.

John H. Reif, Micha Sharir

J. ACM, 1994

Almost Tight Upper Bounds for Lower Envelopes in Higher Dimensions.

Micha Sharir

Discret. Comput. Geom., 1994

New Bounds for Lower Envelopes in Three Dimensions, with Applications to Visbility in Terrains.

Dan Halperin, Micha Sharir

Discret. Comput. Geom., 1994

Castles in the Air Revisited.

Boris Aronov, Micha Sharir

Discret. Comput. Geom., 1994

On the Number of Views of Polyhedral Terrains.

Pankaj K. Agarwal, Micha Sharir

Discret. Comput. Geom., 1994

External Polygon Containment Problems.

Micha Sharir, Sivan Toledo

Comput. Geom., 1994

Computing the Smallest K-enclosing Circle and Related Problems.

Alon Efrat, Micha Sharir, Alon Ziv

Comput. Geom., 1994

An Improved Technique for Output-Sensitive Hidden Surface Removal.

Mark H. Overmars, Micha Sharir

Algorithmica, 1994

Algorithms for Bichromatic Line-Segment Problems Polyhedral Terrains.

Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir

Algorithmica, 1994

Ray Shooting in Polygons Using Geodesic Triangulations.

Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas J. Guibas, John Hershberger, Micha Sharir, Jack Snoeyink

Algorithmica, 1994

Planar Geometric Location Problems.

Pankaj K. Agarwal, Micha Sharir

Algorithmica, 1994

Computing Depth Orders and Related Problems.

Pankaj K. Agarwal, Matthew J. Katz, Micha Sharir

Proceedings of the Algorithm Theory, 1994

Partial surface and volume matching in three dimensions.

Gill Barequet, Micha Sharir

Proceedings of the 12th IAPR International Conference on Pattern Recognition, 1994

On Translational Motion Planning in 3-Space.

Boris Aronov, Micha Sharir

Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

1993

On the Zone Theorem for Hyperplane Arrangements.

Herbert Edelsbrunner, Raimund Seidel, Micha Sharir

SIAM J. Comput., 1993

Computing a Face in an Arrangement of Line Segments and Related Problems.

Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Jack Snoeyink

SIAM J. Comput., 1993

Counting Circular Arc Intersections.

Pankaj K. Agarwal, Marco Pellegrini, Micha Sharir

SIAM J. Comput., 1993

Circle Shooting in a Simple Polygon.

Pankaj K. Agarwal, Micha Sharir

J. Algorithms, 1993

Computing a Segment Center for a Planar Point Set.

Pankaj K. Agarwal, Alon Efrat, Micha Sharir, Sivan Toledo

J. Algorithms, 1993

Optimal Slope Selection via Expanders.

Matthew J. Katz, Micha Sharir

Inf. Process. Lett., 1993

Circular visibility of a simple polygon from a fixed point.

Pankaj K. Agarwal, Micha Sharir

Int. J. Comput. Geom. Appl., 1993

The Upper Envelope of voronoi Surfaces and Its Applications.

Daniel P. Huttenlocher, Klara Kedem, Micha Sharir

Discret. Comput. Geom., 1993

Diameter, Width, Closest Line Pair, and Parametric Searching.

Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir

Discret. Comput. Geom., 1993

On the Zone of a Surface in a Hyperplane Arrangement.

Boris Aronov, Marco Pellegrini, Micha Sharir

Discret. Comput. Geom., 1993

An Invariant Property of Balls in Arrangements of Hyperplanes.

Boris Aronov, Daniel Q. Naiman, János Pach, Micha Sharir

Discret. Comput. Geom., 1993

Applications of a New Space-Partitioning Technique.

Pankaj K. Agarwal, Micha Sharir

Discret. Comput. Geom., 1993

Tail Estimates for the Efficiency of Randomized Incremental Algorithms for Line Segment Intersection.

Kurt Mehlhorn, Micha Sharir, Emo Welzl

Comput. Geom., 1993

On the Union of Fat Wedges and Separating a Collection of Segments By a Line.

Alon Efrat, Günter Rote, Micha Sharir

Comput. Geom., 1993

k-sets and random hulls.

Micha Sharir

Comb., 1993

Selecting Distances in the Plane.

Pankaj K. Agarwal, Boris Aronov, Micha Sharir, Subhash Suri

Algorithmica, 1993

Ray Shooting Amidst Convex Polytopes in Three Dimensions.

Pankaj K. Agarwal, Micha Sharir

Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

Near-Quadratic Bounds for the Motion Planning Problem for a Polygon in a Polygonal Environment

Dan Halperin, Micha Sharir

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

The Union of Convex Polyhedra in Three Dimensions

Boris Aronov, Micha Sharir

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Implementation of a Motion Planning System in Three Dimensions.

Estarose Wolfson, Micha Sharir

Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

The Power of Geometric Duality and Minkowski Sums in Optical Computational Geometry.

Y. B. Karasik, Micha Sharir

Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

New Bounds for Lower Envelopes in Three Dimensions, with Applications to Visibility in Terrains.

Dan Halperin, Micha Sharir

Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, 1993

Arrangements of Surfaces in Higher Dimensions: Envelopes Single Cells and Other Recent Developments.

Micha Sharir

Proceedings of the 5th Canadian Conference on Computational Geometry, 1993

On Critical Orientations in the Kedem-Sharir Motion Planning Algorithm for a Convex Polygon in the Plane.

Klara Kedem, Micha Sharir, Sivan Toledo

Proceedings of the 5th Canadian Conference on Computational Geometry, 1993

Finding Maximally Consistent Sets of Halfspaces.

Alon Efrat, Micha Lindenbaum, Micha Sharir

Proceedings of the 5th Canadian Conference on Computational Geometry, 1993

1992

A Simple Output-Sensitive Algorithm for Hidden Surface Removal.

Micha Sharir, Mark H. Overmars

ACM Trans. Graph., 1992

Arrangements of Curves in the Plane - Topology, Combinatorics and Algorithms.

Herbert Edelsbrunner, Leonidas J. Guibas, János Pach, Richard Pollack, Raimund Seidel, Micha Sharir

Theor. Comput. Sci., 1992

Efficient Motion Planning for an L-Shaped Object.

Dan Halperin, Mark H. Overmars, Micha Sharir

SIAM J. Comput., 1992

Repeated Angles in the Plane and Related Problems.

János Pach, Micha Sharir

J. Comb. Theory A, 1992

Efficient Hidden Surface Removal for Objects with Small Union Size.

Matthew J. Katz, Mark H. Overmars, Micha Sharir

Comput. Geom., 1992

The number of edges of many faces in a line segment arrangement.

Boris Aronov, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir

Comb., 1992

Finding Effective "Force Targets" for Two-Dimensional Multifinger Frictional Grips.

Jacob T. Schwartz, Micha Sharir

Algorithmica, 1992

Randomized Incremental Construction of Delaunay and Voronoi Diagrams.

Leonidas J. Guibas, Donald E. Knuth, Micha Sharir

Algorithmica, 1992

Quasi-Optimal Upper Bounds for Simplex Range Searching and New Zone Theorems.

Bernard Chazelle, Micha Sharir, Emo Welzl

Algorithmica, 1992

A Combinatorial Bound for Linear Programming and Related Problems.

Micha Sharir, Emo Welzl

Proceedings of the STACS 92, 1992

Tail Estimates for the Space Complexity of Randomized Incremental Algorithms.

Kurt Mehlhorn, Micha Sharir, Emo Welzl

Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Optical Computational Geometry.

Y. B. Karasik, Micha Sharir

Proceedings of the Eighth Annual Symposium on Computational Geometry, 1992

1991

A Singly Exponential Stratification Scheme for Real Semi-Algebraic Varieties and its Applications.

Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir

Theor. Comput. Sci., 1991

On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm.

János Pach, Micha Sharir

SIAM J. Comput., 1991

On Disjoint Concave Chains in Arrangements of (Pseudo) Lines.

Dan Halperin, Micha Sharir

Inf. Process. Lett., 1991

Tight bounds on a problem of lines and intersections.

Micha Sharir, Steven Skiena

Discret. Math., 1991

On k-Sets in Arrangement of Curves and Surfaces.

Micha Sharir

Discret. Comput. Geom., 1991

Points and Triangles in the Plane and Halving Planes in Space.

Boris Aronov, Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Rephael Wenger

Discret. Comput. Geom., 1991

Merging Visibility Maps.

Mark H. Overmars, Micha Sharir

Comput. Geom., 1991

Improved Combinatorial Bounds and Efficient Techniques for Certain Motion Planning Problems with Three Degrees of Freedom.

Dan Halperin, Micha Sharir

Comput. Geom., 1991

Counting and Cutting Cycles of Lines and Rods in Space.

Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Richard Pollack, Raimund Seidel, Micha Sharir, Jack Snoeyink

Comput. Geom., 1991

Off-line Dynamic Maintenance of the Width of a Planar Point Set.

Pankaj K. Agarwal, Micha Sharir

Comput. Geom., 1991

Coordinated Motion Planning for Two Independent Robots.

Micha Sharir, Shmuel Sifrony

Ann. Math. Artif. Intell., 1991

On the Zone of a Surface in a Hyperplane Arrangement.

Boris Aronov, Micha Sharir

Proceedings of the Algorithms and Data Structures, 1991

Computing a Face in an Arrangement of Line Segments.

Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Jack Snoeyink

Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

Planar Geometric Location Problems and Maintaining the Width of a Planar Set.

Pankaj K. Agarwal, Micha Sharir

Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

Fat Triangles Determine Linearly Many Holes

Jirí Matousek, Nathaly Miller, János Pach, Micha Sharir, Shmuel Sifrony, Emo Welzl

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Counting Circular Arc Intersections.

Pankaj K. Agarwal, Micha Sharir

Proceedings of the Seventh Annual Symposium on Computational Geometry, 1991

1990

Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection.

Pankaj K. Agarwal, Micha Sharir

SIAM J. Comput., 1990

On the Two-Dimensional Davenport Schinzel Problem.

Jacob T. Schwartz, Micha Sharir

J. Symb. Comput., 1990

An Algorithm for Generalized Point Location and its Applications.

Bernard Chazelle, Micha Sharir

J. Symb. Comput., 1990

An Efficient Motion-planning Algorithm for a Convex Polygonal Object in Two Dimensional Polygonal Space.

Klara Kedem, Micha Sharir

Discret. Comput. Geom., 1990

The Maximum Number of Ways To Stab n Convex Nonintersecting Sets in the Plane Is 2n-2.

Herbert Edelsbrunner, Micha Sharir

Discret. Comput. Geom., 1990

The Complexity of Many Cells in Arrangements of Planes and Related Problems.

Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir

Discret. Comput. Geom., 1990

The Complexity and Construction of Many Faces in Arrangement of Lines and of Segments.

Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir

Discret. Comput. Geom., 1990

Combinatorial Complexity Bounds for Arrangement of Curves and Spheres.

Kenneth L. Clarkson, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Emo Welzl

Discret. Comput. Geom., 1990

The Caratheodory number for the k-core.

Imre Bárány, Micha Sharir

Comb., 1990

Triangles in space or building (and analyzing) castles in the air.

Boris Aronov, Micha Sharir

Comb., 1990

Storing Line Segments in Partition Trees.

Mark H. Overmars, Haijo Schipper, Micha Sharir

BIT, 1990

A Hyperplane Incidence Problem with Applications to Counting Distances.

Herbert Edelsbrunner, Micha Sharir

Proceedings of the Algorithms, 1990

Slimming Down by Adding: Selecting Heavily Covered Points.

Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, John Hershberger, Raimund Seidel, Micha Sharir

Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

The Combinatorial Complexity of Hyperplane Transversals.

Sylvain E. Cappell, Jacob E. Goodman, János Pach, Richard Pollack, Micha Sharir, Rephael Wenger

Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

An Automatic Motion Planning System for a Convex Polygonal Mobile Robot in 2-Dimensional Polygonal Space.

Klara Kedem, Micha Sharir

Proceedings of the Autonomous Robot Vehicles, 1990

Algorithmic Motion Planning in Robotics.

Jacob T. Schwartz, Micha Sharir

Proceedings of the Handbook of Theoretical Computer Science, 1990

1989

Visibility Problems for Polyhedral Terrains.

Richard Cole, Micha Sharir

J. Symb. Comput., 1989

Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences.

Pankaj K. Agarwal, Micha Sharir, Peter W. Shor

J. Comb. Theory A, 1989

A Note on the Papadimitriou-Silverberg Algorithm for Planning Optimal Piecewise-Linear Motion of a Ladder.

Micha Sharir

Inf. Process. Lett., 1989

Computing the Geodesic Center of a Simple Polygon.

Richard Pollack, Micha Sharir, Günter Rote

Discret. Comput. Geom., 1989

The Upper Envelope of Piecewise Linear Functions and the Boundary of a Region Enclosed by Convex Plates: Combinatorial Analysis.

János Pach, Micha Sharir

Discret. Comput. Geom., 1989

On the General Motion-Planning Problem with Two Degrees of Freedom.

Leonidas J. Guibas, Micha Sharir, Shmuel Sifrony

Discret. Comput. Geom., 1989

The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications.

Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir

Discret. Comput. Geom., 1989

Implicitly Representing Arrangements of Lines or Segments.

Herbert Edelsbrunner, Leonidas J. Guibas, John Hershberger, Raimund Seidel, Micha Sharir, Jack Snoeyink, Emo Welzl

Discret. Comput. Geom., 1989

On Arrangement of Jordan Arcs with Three Intersection per Pair.

Herbert Edelsbrunner, Leonidas J. Guibas, John Hershberger, János Pach, Richard Pollack, Raimund Seidel, Micha Sharir, Jack Snoeyink

Discret. Comput. Geom., 1989

Algorithmic Motion Planning in Robotics.

Micha Sharir

Computer, 1989

Lines in Space-Combinatorics, Algorithms and Applications

Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

A Singly-Expenential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications.

Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir

Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

Output-Sensitive Hidden Surface Removal

Mark H. Overmars, Micha Sharir

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988

On the shortest paths between two convex polyhedra.

Avikam Baltsan, Micha Sharir

J. ACM, 1988

The Shortest Watchtower and Related Problems for Polyhedral Terrains.

Micha Sharir

Inf. Process. Lett., 1988

Planar Realizations of Nonlinear Davenport-Schnitzel Sequences by Segments.

Ady Wiernik, Micha Sharir

Discret. Comput. Geom., 1988

Separating Two Simple Polygons by a Sequence of Translations.

Ricky Pollack, Micha Sharir, Shmuel Sifrony

Discret. Comput. Geom., 1988

Computing the Link Center of a Simple Polygon.

William J. Lenhart, Richard Pollack, Jörg-Rüdiger Sack, Raimund Seidel, Micha Sharir, Subhash Suri, Godfried T. Toussaint, Sue Whitesides, Chee-Keng Yap

Discret. Comput. Geom., 1988

Improved lower bounds on the length of Davenport - Schinzel sequences.

Micha Sharir

Comb., 1988

A Survey of Motion Planning and Related Geometric Algorithms.

Jacob T. Schwartz, Micha Sharir

Artif. Intell., 1988

Intersecting Line Segments, Ray Shooting, and Other Applications of Geometric Partitioning Techniques.

Leonidas J. Guibas, Mark H. Overmars, Micha Sharir

Proceedings of the SWAT 88, 1988

Theoretical and experimental studies using a multifinger planar manipulator.

James Demmel, Gerardo Lafferriere, Jacob T. Schwartz, Micha Sharir

Proceedings of the 1988 IEEE International Conference on Robotics and Automation, 1988

Combinatorial Complexity Bounds for Arrangements of Curves and Surfaces

Kenneth L. Clarkson, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Emo Welzl

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

An Automatic Motion Planning System for a Convex Polygonal Mobile Robot in 2-Dimensional Polygonal Space.

Klara Kedem, Micha Sharir

Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

The Complexity of Many Faces in Arrangements of Lines and of Segments.

Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir

Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

On Arrangements of Jordan Arcs with Three Intersections per Pair.

Herbert Edelsbrunner, Leonidas J. Guibas, John Hershberger, János Pach, Richard Pollack, Raimund Seidel, Micha Sharir, Jack Snoeyink

Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

1987

On Shortest Paths Amidst Convex Polyhedra.

Micha Sharir

SIAM J. Comput., 1987

On k-Hulls and Related Problems.

Richard Cole, Micha Sharir, Chee-Keng Yap

SIAM J. Comput., 1987

An Efficient and Simple Motion Planning Algorithm for a Ladder Amidst Polygonal Barriers.

Daniel Leven, Micha Sharir

J. Algorithms, 1987

On the Number of Critical Free Contacts of a Convex Polygonal Object Moving in Two-Dimensional Polygonal Space.

Daniel Leven, Micha Sharir

Discret. Comput. Geom., 1987

Planning a Purely Translational Motion for a Convex Object in Two-Dimensional Space Using Generalized Voronoi Diagrams.

Daniel Leven, Micha Sharir

Discret. Comput. Geom., 1987

Almost linear upper bounds on the length of general Davenport-Schinzel sequences.

Micha Sharir

Comb., 1987

A New Efficient Motion-Planning Algorithm for a Rod in Two-Dimensional Polygonal Space.

Shmuel Sifrony, Micha Sharir

Algorithmica, 1987

Generalized Voronoi Diagrams for a Ladder: II. Efficient Construction of the Diagram.

Colm Ó'Dúnlaing, Micha Sharir, Chee-Keng Yap

Algorithmica, 1987

On the Existence and Synthesis of Multifinger Positive Grips.

Bhubaneswar Mishra, Jacob T. Schwartz, Micha Sharir

Algorithmica, 1987

Linear-Time Algorithms for Visibility and Shortest Path Problems Inside Triangulated Simple Polygons.

Leonidas J. Guibas, John Hershberger, Daniel Leven, Micha Sharir, Robert Endre Tarjan

Algorithmica, 1987

Efficient algorithms for planning purely translational collision-free motion in two and three dimensions.

Micha Sharir

Proceedings of the 1987 IEEE International Conference on Robotics and Automation, Raleigh, North Carolina, USA, March 31, 1987

On the Bivariate Function Minimization Problem And Its Applications to Motion Planning.

Jacob T. Schwartz, Micha Sharir

Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987

On the Lower Envelope of Bivariate Functions and its Applications

Herbert Edelsbrunner, János Pach, Jacob T. Schwartz, Micha Sharir

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1986

On Shortest Paths in Polyhedral Spaces.

Micha Sharir, Amir Schorr

SIAM J. Comput., 1986

Object recognition by three-dimensional curve matching.

C. Marc Bastuscheck, Edith Schonberg, Jacob T. Schwartz, Micha Sharir

Int. J. Intell. Syst., 1986

Probabilistic Propositional Temporal Logics

Sergiu Hart, Micha Sharir

Inf. Control., 1986

On the Union of Jordan Regions and Collision-Free Translational Motion Amidst Polygonal Obstacles.

Klara Kedem, Ron Livne, János Pach, Micha Sharir

Discret. Comput. Geom., 1986

Nonlinearity of Davenport - Schinzel sequences and of generalized path compression schemes.

Sergiu Hart, Micha Sharir

Comb., 1986

Geometric Applications of Davenport-Schinzel Sequences

Micha Sharir, Richard Cole, Klara Kedem, Daniel Leven, Richard Pollack, Shmuel Sifrony

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

A New Efficient Motion-Planning Algorithm for a Rod in Polygonal Space.

Shmuel Sifrony, Micha Sharir

Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, 1986

On Shortest Paths Amidst Convex Polyhedra.

Micha Sharir, Avikam Baltsan

Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, 1986

Linear Time Algorithms for Visibility and Shortest Path Problems Inside Simple Polygons.

Leonidas J. Guibas, John Hershberger, Daniel Leven, Micha Sharir, Robert Endre Tarjan

Proceedings of the Second Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry, 1986

1985

Intersection and Closest-Pair Problems for a Set of Planar Discs.

Micha Sharir

SIAM J. Comput., 1985

Concurrent Probabilistic Programs, Or: How to Schedule if You Must.

Sergiu Hart, Micha Sharir

SIAM J. Comput., 1985

On Minima of Functions, Intersection Patterns of Curves, and Davenport-Schinzel Sequences

Micha Sharir, Ron Livne

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

An efficient and simple motion planning algorithm for a ladder moving in two-dimensional space amidst polygonal barriers (extended abstract).

Daniel Leven, Micha Sharir

Proceedings of the First Annual Symposium on Computational Geometry, 1985

An efficient algorithm for planning collision-free translational motion of a convex polygonal object in 2-dimensional space amidst polygonal obstacles.

Klara Kedem, Micha Sharir

Proceedings of the First Annual Symposium on Computational Geometry, 1985

1984

Verification of Probabilistic Programs.

Micha Sharir, Amir Pnueli, Sergiu Hart

SIAM J. Comput., 1984

Probabilistic Temporal Logics for Finite and Bounded Models

Sergiu Hart, Micha Sharir

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

Nonlinearity of Davenport-Schinzel Sequences and of a Generalized Path Compression Scheme

Sergiu Hart, Micha Sharir

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983

Termination of Probabilistic Concurrent Program.

Sergiu Hart, Micha Sharir, Amir Pnueli

ACM Trans. Program. Lang. Syst., 1983

Experience with the SETL Optimizer.

Stefan M. Freudenberger, Jacob T. Schwartz, Micha Sharir

ACM Trans. Program. Lang. Syst., 1983

Retraction: A New Approach to Motion-Planning (Extended Abstract)

Colm Ó'Dúnlaing, Micha Sharir, Chee-Keng Yap

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Concurrent Probabilistic Program, or: How to Schedule if You Must.

Sergiu Hart, Micha Sharir

Proceedings of the Automata, 1983

1982

Some Observations Concerning Formal Differentiation of Set Theoretic Expressions.

Micha Sharir

ACM Trans. Program. Lang. Syst., 1982

Transformational Derivation of a Garbage Collection Algorithm.

Robert B. K. Dewar, Micha Sharir, Elia Weixelbaum

ACM Trans. Program. Lang. Syst., 1982

Fast Composition of Sparse Maps.

Micha Sharir

Inf. Process. Lett., 1982

Some Modified Algorithms for Dijkstra's Longest Upsequence Problem.

Robert B. K. Dewar, Susan M. Merritt, Micha Sharir

Acta Informatica, 1982

Termination of Probabilistic Concurrent Programs.

Sergiu Hart, Micha Sharir, Amir Pnueli

Proceedings of the Conference Record of the Ninth Annual ACM Symposium on Principles of Programming Languages, 1982

1981

An Automatic Technique for Selection of Data Structures in SETL Programs.

Edmond Schonberg, Jacob T. Schwartz, Micha Sharir

ACM Trans. Program. Lang. Syst., 1981

Formal Integration: A Program Transformation Technique.

Micha Sharir

Comput. Lang., 1981

Data Flow Analysis of Applicative Programs.

Micha Sharir

Proceedings of the Automata, 1981

1980

Structural Analysis: A New Approch to Flow Analysis in Optimizing Compilers.

Micha Sharir

Comput. Lang., 1980

1979

The design of a global optimizer.

Ronald J. Mintz, Gerald A. Fisher, Micha Sharir

Proceedings of the 1979 SIGPLAN Symposium on Compiler Construction, 1979

Automatic Data Structure Selection in SETL.

Edmond Schonberg, Jacob T. Schwartz, Micha Sharir

Proceedings of the Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, 1979