Ezra, Esther; Sharir, Micha On ray shooting for triangles in 3-space and related problems. (English) Zbl 1502.68317 SIAM J. Comput. 51, No. 4, 1065-1095 (2022). Reviewer: Gabriela Cristescu (Arad) MSC: 68U05 52C35 52C45 68P05 68Q25 PDFBibTeX XMLCite \textit{E. Ezra} and \textit{M. Sharir}, SIAM J. Comput. 51, No. 4, 1065--1095 (2022; Zbl 1502.68317) Full Text: DOI arXiv
Gawrychowski, Paweł; Kaplan, Haim; Mozes, Shay; Sharir, Micha; Weimann, Oren Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time. (English) Zbl 1517.68294 SIAM J. Comput. 50, No. 2, 509-554 (2021). Reviewer: Haiko Müller (Leeds) MSC: 68R10 05C10 05C12 05C85 68U05 68W40 PDFBibTeX XMLCite \textit{P. Gawrychowski} et al., SIAM J. Comput. 50, No. 2, 509--554 (2021; Zbl 1517.68294) Full Text: DOI
Aiger, Dror; Kaplan, Haim; Sharir, Micha Reporting neighbors in high-dimensional Euclidean space. (English) Zbl 1360.68866 SIAM J. Comput. 43, No. 4, 1363-1395 (2014). MSC: 68U05 68W20 68W40 PDFBibTeX XMLCite \textit{D. Aiger} et al., SIAM J. Comput. 43, No. 4, 1363--1395 (2014; Zbl 1360.68866) Full Text: DOI
Aronov, Boris; de Berg, Mark; Ezra, Esther; Sharir, Micha Improved bounds for the union of locally fat objects in the plane. (English) Zbl 1295.05258 SIAM J. Comput. 43, No. 2, 543-572 (2014). MSC: 05D99 52C45 68U05 68R05 PDFBibTeX XMLCite \textit{B. Aronov} et al., SIAM J. Comput. 43, No. 2, 543--572 (2014; Zbl 1295.05258) Full Text: DOI Link
Agarwal, Pankaj K.; Ben Avraham, Rinat; Kaplan, Haim; Sharir, Micha Computing the discrete Fréchet distance in subquadratic time. (English) Zbl 1297.68226 SIAM J. Comput. 43, No. 2, 429-449 (2014). MSC: 68U05 68Q45 PDFBibTeX XMLCite \textit{P. K. Agarwal} et al., SIAM J. Comput. 43, No. 2, 429--449 (2014; Zbl 1297.68226) Full Text: DOI arXiv
Agarwal, Pankaj K.; Matoušek, Jiří; Sharir, Micha On range searching with semialgebraic sets. II. (English) Zbl 1285.68192 SIAM J. Comput. 42, No. 6, 2039-2062 (2013). MSC: 68U05 14P10 52C45 68P05 PDFBibTeX XMLCite \textit{P. K. Agarwal} et al., SIAM J. Comput. 42, No. 6, 2039--2062 (2013; Zbl 1285.68192) Full Text: DOI arXiv
Rubin, Natan; Sharir, Micha Improved bounds for geometric permutations. (English) Zbl 1255.52008 SIAM J. Comput. 41, No. 2, 367-390 (2012). Reviewer: Vladimir Golubyatnikov (Novosibirsk) MSC: 52A20 52C45 68U05 52A15 PDFBibTeX XMLCite \textit{N. Rubin} and \textit{M. Sharir}, SIAM J. Comput. 41, No. 2, 367--390 (2012; Zbl 1255.52008) Full Text: DOI arXiv
Kaplan, Haim; Katz, Matthew J.; Morgenstern, Gila; Sharir, Micha Optimal cover of points by disks in a simple polygon. (English) Zbl 1234.68443 SIAM J. Comput. 40, No. 6, 1647-1661 (2011). MSC: 68U05 52C15 68W40 05C17 PDFBibTeX XMLCite \textit{H. Kaplan} et al., SIAM J. Comput. 40, No. 6, 1647--1661 (2011; Zbl 1234.68443) Full Text: DOI
Sharir, Micha; Shaul, Hayim Semialgebraic range reporting and emptiness searching with applications. (English) Zbl 1228.68058 SIAM J. Comput. 40, No. 4, 1045-1074 (2011). MSC: 68U05 68P05 68P10 68Q25 68W20 68W40 PDFBibTeX XMLCite \textit{M. Sharir} and \textit{H. Shaul}, SIAM J. Comput. 40, No. 4, 1045--1074 (2011; Zbl 1228.68058) Full Text: DOI arXiv
Kaplan, Haim; Rubin, Natan; Sharir, Micha Line transversals of convex polyhedra in \(\mathbb{R}^3\). (English) Zbl 1211.52010 SIAM J. Comput. 39, No. 7, 3283-3310 (2010). MSC: 52B05 52B10 52C35 52C45 65D18 68Q25 68U05 PDFBibTeX XMLCite \textit{H. Kaplan} et al., SIAM J. Comput. 39, No. 7, 3283--3310 (2010; Zbl 1211.52010) Full Text: DOI
Aronov, Boris; Ezra, Esther; Sharir, Micha Small-size \(\varepsilon\)-nets for axis-parallel rectangles and boxes. (English) Zbl 1209.68624 SIAM J. Comput. 39, No. 7, 3248-3282 (2010). MSC: 68W20 52C45 68U05 68W25 PDFBibTeX XMLCite \textit{B. Aronov} et al., SIAM J. Comput. 39, No. 7, 3248--3282 (2010; Zbl 1209.68624) Full Text: DOI
Aronov, Boris; Sharir, Micha Approximate halfspace range counting. (English) Zbl 1216.68079 SIAM J. Comput. 39, No. 7, 2704-2725 (2010). MSC: 68P05 68P10 68Q25 68Q87 68W20 68W25 68W40 PDFBibTeX XMLCite \textit{B. Aronov} and \textit{M. Sharir}, SIAM J. Comput. 39, No. 7, 2704--2725 (2010; Zbl 1216.68079) Full Text: DOI Link
Kaplan, Haim; Rubin, Natan; Sharir, Micha; Verbin, Elad Efficient colored orthogonal range counting. (English) Zbl 1187.68172 SIAM J. Comput. 38, No. 3, 982-1011 (2008). MSC: 68P05 68Q25 68U05 65D18 52C45 52C35 PDFBibTeX XMLCite \textit{H. Kaplan} et al., SIAM J. Comput. 38, No. 3, 982--1011 (2008; Zbl 1187.68172) Full Text: DOI
Chen, Ke; Fiat, Amos; Kaplan, Haim; Levy, Meital; Matoušek, Jiří; Mossel, Elchanan; Pach, János; Sharir, Micha; Smorodinsky, Shakhar; Wagner, Uli; Welzl, Emo Online conflict-free coloring for intervals. (English) Zbl 1124.68077 SIAM J. Comput. 36, No. 5, 1342-1359 (2006). MSC: 68R10 05C15 52C45 68Q25 68W20 68W40 PDFBibTeX XMLCite \textit{K. Chen} et al., SIAM J. Comput. 36, No. 5, 1342--1359 (2006; Zbl 1124.68077) Full Text: DOI
Agarwal, Pankaj K.; Overmars, Mark; Sharir, Micha Computing maximally separated sets in the plane. (English) Zbl 1120.68102 SIAM J. Comput. 36, No. 3, 815-834 (2006). MSC: 68U05 68Q25 68W25 PDFBibTeX XMLCite \textit{P. K. Agarwal} et al., SIAM J. Comput. 36, No. 3, 815--834 (2006; Zbl 1120.68102) Full Text: DOI
Sharir, Micha; Welzl, Emo On the number of crossing-free matchings, cycles, and partitions. (English) Zbl 1120.68085 SIAM J. Comput. 36, No. 3, 695-720 (2006). MSC: 68R10 68R05 52C45 68U05 PDFBibTeX XMLCite \textit{M. Sharir} and \textit{E. Welzl}, SIAM J. Comput. 36, No. 3, 695--720 (2006; Zbl 1120.68085) Full Text: DOI
Ezra, Esther; Sharir, Micha Output-sensitive construction of the union of triangles. (English) Zbl 1087.68118 SIAM J. Comput. 34, No. 6, 1331-1351 (2005). MSC: 68U05 52C45 05D99 51F99 68W20 PDFBibTeX XMLCite \textit{E. Ezra} and \textit{M. Sharir}, SIAM J. Comput. 34, No. 6, 1331--1351 (2005; Zbl 1087.68118) Full Text: DOI
Koltun, Vladlen; Sharir, Micha Curve-sensitive cuttings. (English) Zbl 1075.68093 SIAM J. Comput. 34, No. 4, 863-878 (2005). MSC: 68U05 52C45 68W20 PDFBibTeX XMLCite \textit{V. Koltun} and \textit{M. Sharir}, SIAM J. Comput. 34, No. 4, 863--878 (2005; Zbl 1075.68093) Full Text: DOI
Agarwal, Pankaj K.; Sharir, Micha Pseudo-line arrangements: Duality, algorithms, and applications. (English) Zbl 1077.52516 SIAM J. Comput. 34, No. 3, 526-552 (2005). MSC: 52C30 52C35 68W40 PDFBibTeX XMLCite \textit{P. K. Agarwal} and \textit{M. Sharir}, SIAM J. Comput. 34, No. 3, 526--552 (2005; Zbl 1077.52516) Full Text: DOI
Seidel, Raimund; Sharir, Micha Top-down analysis of path compression. (English) Zbl 1075.68105 SIAM J. Comput. 34, No. 3, 515-525 (2005). MSC: 68W40 68P05 PDFBibTeX XMLCite \textit{R. Seidel} and \textit{M. Sharir}, SIAM J. Comput. 34, No. 3, 515--525 (2005; Zbl 1075.68105) Full Text: DOI
Kaibel, Volker; Mechtel, Rafael; Sharir, Micha; Ziegler, Günter M. The simplex algorithm in dimension three. (English) Zbl 1121.65327 SIAM J. Comput. 34, No. 2, 475-497 (2005). MSC: 65K05 90C05 90C35 PDFBibTeX XMLCite \textit{V. Kaibel} et al., SIAM J. Comput. 34, No. 2, 475--497 (2005; Zbl 1121.65327) Full Text: DOI arXiv
Koltun, Vladlen; Sharir, Micha The partition technique for overlays of envelopes. (English) Zbl 1052.68132 SIAM J. Comput. 32, No. 4, 841-863 (2003). MSC: 68U05 52C45 68Q25 PDFBibTeX XMLCite \textit{V. Koltun} and \textit{M. Sharir}, SIAM J. Comput. 32, No. 4, 841--863 (2003; Zbl 1052.68132) Full Text: DOI
Koltun, Vladlen; Sharir, Micha 3-dimensional Euclidean Voronoi diagrams of lines with a fixed number of orientations. (English) Zbl 1046.68114 SIAM J. Comput. 32, No. 3, 616-642 (2003). MSC: 68U05 52C45 68Q25 14P99 51N20 PDFBibTeX XMLCite \textit{V. Koltun} and \textit{M. Sharir}, SIAM J. Comput. 32, No. 3, 616--642 (2003; Zbl 1046.68114) Full Text: DOI
Agarwal, Pankaj K.; Efrat, Alon; Sharir, Micha Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications. (English) Zbl 0949.68179 SIAM J. Comput. 29, No. 3, 912-953 (2000). Reviewer: Jonathan Hodgson (Philadelphia) MSC: 68W40 68R05 68U05 57N80 05C99 PDFBibTeX XMLCite \textit{P. K. Agarwal} et al., SIAM J. Comput. 29, No. 3, 912--953 (2000; Zbl 0949.68179) Full Text: DOI
Aronov, Boris; Sharir, Micha On translational motion planning of a convex polyhedron in 3-space. (English) Zbl 0891.68118 SIAM J. Comput. 26, No. 6, 1785-1803 (1997). MSC: 68U05 52B10 52B55 65D18 68Q25 PDFBibTeX XMLCite \textit{B. Aronov} and \textit{M. Sharir}, SIAM J. Comput. 26, No. 6, 1785--1803 (1997; Zbl 0891.68118) Full Text: DOI
Agarwal, Pankaj K.; Aronov, Boris; Sharir, Micha Computing envelopes in four dimensions with applications. (English) Zbl 0885.68072 SIAM J. Comput. 26, No. 6, 1714-1732 (1997). MSC: 68W10 68Q25 68R05 68U05 PDFBibTeX XMLCite \textit{P. K. Agarwal} et al., SIAM J. Comput. 26, No. 6, 1714--1732 (1997; Zbl 0885.68072) Full Text: DOI
Aronov, Boris; Sharir, Micha; Tagansky, Boaz The union of convex polyhedra in three dimensions. (English) Zbl 0891.68116 SIAM J. Comput. 26, No. 6, 1670-1688 (1997). MSC: 68U05 68Q25 52B10 52B55 65D18 PDFBibTeX XMLCite \textit{B. Aronov} et al., SIAM J. Comput. 26, No. 6, 1670--1688 (1997; Zbl 0891.68116) Full Text: DOI
Katz, Matthew J.; Sharir, Micha An expander-based approach to geometric optimization. (English) Zbl 0888.68116 SIAM J. Comput. 26, No. 5, 1384-1408 (1997). MSC: 68U05 05C99 68W10 68R10 52C99 90B80 PDFBibTeX XMLCite \textit{M. J. Katz} and \textit{M. Sharir}, SIAM J. Comput. 26, No. 5, 1384--1408 (1997; Zbl 0888.68116) Full Text: DOI
Mohaban, Shai; Sharir, Micha Ray shooting amidst spheres in three dimensions and related problems. (English) Zbl 0874.68284 SIAM J. Comput. 26, No. 3, 654-674 (1997). MSC: 68U05 68P05 68Q25 52B11 68W10 PDFBibTeX XMLCite \textit{S. Mohaban} and \textit{M. Sharir}, SIAM J. Comput. 26, No. 3, 654--674 (1997; Zbl 0874.68284) Full Text: DOI
Agarwal, Pankaj K.; Sharir, Micha Ray shooting amidst convex polyhedra and polyhedral terrains in three dimensions. (English) Zbl 0843.68116 SIAM J. Comput. 25, No. 1, 100-116 (1996). MSC: 68U05 52B11 68P05 68W10 68Q25 PDFBibTeX XMLCite \textit{P. K. Agarwal} and \textit{M. Sharir}, SIAM J. Comput. 25, No. 1, 100--116 (1996; Zbl 0843.68116) Full Text: DOI
Chazelle, Bernard; Edelsbrunner, Herbert; Guibas, Leonidas J.; Hershberger, John E.; Seidel, Raimund; Sharir, Micha Selecting heavily covered points. (English) Zbl 0813.68157 SIAM J. Comput. 23, No. 6, 1138-1151 (1994). MSC: 68U05 05B99 68R10 51M99 52A99 68W10 PDFBibTeX XMLCite \textit{B. Chazelle} et al., SIAM J. Comput. 23, No. 6, 1138--1151 (1994; Zbl 0813.68157) Full Text: DOI
Matoušek, Jiří; Pach, János; Sharir, Micha; Sifrony, Shmuel; Welzl, Emo Fat triangles determine linearly many holes. (English) Zbl 0802.68152 SIAM J. Comput. 23, No. 1, 154-169 (1994). MSC: 68U05 05A99 68Q25 68R05 52A37 52A10 PDFBibTeX XMLCite \textit{J. Matoušek} et al., SIAM J. Comput. 23, No. 1, 154--169 (1994; Zbl 0802.68152) Full Text: DOI
Chazelle, Bernard; Edelsbrunner, Herbert; Guibas, Leonidas; Sharir, Micha; Snoeyink, Jack Computing a face in an arrangement of line segments and related problems. (English) Zbl 0799.68182 SIAM J. Comput. 22, No. 6, 1286-1302 (1993). MSC: 68U05 68W10 68R99 51M99 PDFBibTeX XMLCite \textit{B. Chazelle} et al., SIAM J. Comput. 22, No. 6, 1286--1302 (1993; Zbl 0799.68182) Full Text: DOI
Agarwal, Pankaj K.; Pellegrini, Marco; Sharir, Micha Counting circular arc intersections. (English) Zbl 0789.68137 SIAM J. Comput. 22, No. 4, 778-793 (1993). Reviewer: H.Alt (Berlin) MSC: 68U05 68Q25 52C10 68P05 68W30 PDFBibTeX XMLCite \textit{P. K. Agarwal} et al., SIAM J. Comput. 22, No. 4, 778--793 (1993; Zbl 0789.68137) Full Text: DOI
Edelsbrunner, Herbert; Seidel, Raimund; Sharir, Micha On the zone theorem for hyperplane arrangements. (English) Zbl 0778.52007 SIAM J. Comput. 22, No. 2, 418-429 (1993). Reviewer: H.-D.Hecker (Jena) MSC: 52C35 68U05 PDFBibTeX XMLCite \textit{H. Edelsbrunner} et al., SIAM J. Comput. 22, No. 2, 418--429 (1993; Zbl 0778.52007) Full Text: DOI
Halperin, Dan; Overmars, Mark H.; Sharir, Micha Efficient motion planning for an \(L\)-shaped object. (English) Zbl 0743.68129 SIAM J. Comput. 21, No. 1, 1-23 (1992). MSC: 68U05 68Q25 PDFBibTeX XMLCite \textit{D. Halperin} et al., SIAM J. Comput. 21, No. 1, 1--23 (1992; Zbl 0743.68129) Full Text: DOI
Pach, János; Sharir, Micha On vertical visibility in arrangements of segments and the queue size in the Bentley-Ottmann line sweeping algorithm. (English) Zbl 0735.68089 SIAM J. Comput. 20, No. 3, 460-470 (1991). MSC: 68U05 51M99 68Q25 05C99 PDFBibTeX XMLCite \textit{J. Pach} and \textit{M. Sharir}, SIAM J. Comput. 20, No. 3, 460--470 (1991; Zbl 0735.68089) Full Text: DOI
Agarwal, Pankaj K.; Sharir, Micha Red-blue intersection detection algorithms, with applications to motion planning and collision detection. (English) Zbl 0696.68044 SIAM J. Comput. 19, No. 2, 297-321 (1990). Reviewer: H.-D.Hecker MSC: 68Q25 68R99 52A37 68W99 PDFBibTeX XMLCite \textit{P. K. Agarwal} and \textit{M. Sharir}, SIAM J. Comput. 19, No. 2, 297--321 (1990; Zbl 0696.68044) Full Text: DOI
Cole, Richard; Sharir, Micha; Yap, Chee K. On k-hulls and related problems. (English) Zbl 0637.68074 SIAM J. Comput. 16, 61-77 (1987). MSC: 68P10 68Q25 52-04 52A20 PDFBibTeX XMLCite \textit{R. Cole} et al., SIAM J. Comput. 16, 61--77 (1987; Zbl 0637.68074) Full Text: DOI
Sharir, Micha On shortest paths amidst convex polyhedra. (English) Zbl 0619.52006 SIAM J. Comput. 16, 561-572 (1987). Reviewer: E.Jucovič MSC: 52Bxx 05C35 05C38 68U99 PDFBibTeX XMLCite \textit{M. Sharir}, SIAM J. Comput. 16, 561--572 (1987; Zbl 0619.52006) Full Text: DOI
Sharir, Micha; Schorr, Amir On shortest paths in polyhedral spaces. (English) Zbl 0612.68090 SIAM J. Comput. 15, 193-215 (1986). MSC: 68U99 68Q25 52Bxx PDFBibTeX XMLCite \textit{M. Sharir} and \textit{A. Schorr}, SIAM J. Comput. 15, 193--215 (1986; Zbl 0612.68090) Full Text: DOI Backlinks: MO
Hart, Sergiu; Sharir, Micha Concurrent probabilistic programs, or: How to schedule if you must. (English) Zbl 0569.68018 SIAM J. Comput. 14, 991-1012 (1985). MSC: 68N25 68M20 PDFBibTeX XMLCite \textit{S. Hart} and \textit{M. Sharir}, SIAM J. Comput. 14, 991--1012 (1985; Zbl 0569.68018) Full Text: DOI
Sharir, Micha Intersection and closest-pair problems for a set of planar discs. (English) Zbl 0564.68052 SIAM J. Comput. 14, 448-468 (1985). MSC: 68R99 68Q25 PDFBibTeX XMLCite \textit{M. Sharir}, SIAM J. Comput. 14, 448--468 (1985; Zbl 0564.68052) Full Text: DOI
Sharir, Micha; Pnueli, Amir; Hart, Sergiu Verification of probabilistic programs. (English) Zbl 0533.68012 SIAM J. Comput. 13, 292-314 (1984). MSC: 68Q60 PDFBibTeX XMLCite \textit{M. Sharir} et al., SIAM J. Comput. 13, 292--314 (1984; Zbl 0533.68012) Full Text: DOI