×

Found 425 Documents (Results 1–100)

Covering points by hyperplanes and related problems. (English) Zbl 07849055

Goaoc, Xavier (ed.) et al., 38th international symposium on computational geometry, SoCG 2022, Berlin, Germany, June 7–10, 2022. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 224, Article 57, 7 p. (2022).
MSC:  68U05
PDFBibTeX XMLCite
Full Text: DOI

Intersection queries for flat semi-algebraic objects in three dimensions and related problems. (English) Zbl 07849002

Goaoc, Xavier (ed.) et al., 38th international symposium on computational geometry, SoCG 2022, Berlin, Germany, June 7–10, 2022. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 224, Article 4, 14 p. (2022).
MSC:  68U05
PDFBibTeX XMLCite
Full Text: DOI arXiv

Subquadratic algorithms for some 3Sum-hard geometric problems in the algebraic decision tree model. (English) Zbl 1535.68423

Ahn, Hee-Kap (ed.) et al., 32nd international symposium on algorithms and computation, ISAAC 2021, Fukuoka, Japan, December 6–8, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 212, Article 3, 15 p. (2021).
MSC:  68U05 52C30 68W40
PDFBibTeX XMLCite
Full Text: DOI

Incidences between points and curves with almost two degrees of freedom. (English) Zbl 1535.52017

Cabello, Sergio (ed.) et al., 36th international symposium on computational geometry, SoCG 2020, Zürich, Switzerland (virtual conference), June 23–26, 2020. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 164, Article 66, 14 p. (2020).
MSC:  52C10 05D15 14H50
PDFBibTeX XMLCite
Full Text: DOI

How to find a point in the convex hull privately. (English) Zbl 1533.68371

Cabello, Sergio (ed.) et al., 36th international symposium on computational geometry, SoCG 2020, Zürich, Switzerland (virtual conference), June 23–26, 2020. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 164, Article 52, 15 p. (2020).
MSC:  68U05 52B55 68P27
PDFBibTeX XMLCite
Full Text: DOI arXiv

Testing polynomials for vanishing on Cartesian products of planar point sets. (English) Zbl 07760137

Cabello, Sergio (ed.) et al., 36th international symposium on computational geometry, SoCG 2020, Zürich, Switzerland (virtual conference), June 23–26, 2020. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 164, Article 8, 14 p. (2020).
MSC:  68U05
PDFBibTeX XMLCite
Full Text: DOI

On the complexity of the \(k\)-level in arrangements of pseudoplanes. (English) Zbl 07559262

Barequet, Gill (ed.) et al., 35th international symposium on computational geometry, SoCG 2019, Portland, Oregon, USA, June 18–21, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 129, Article 62, 15 p. (2019).
MSC:  68U05
PDFBibTeX XMLCite
Full Text: DOI

General techniques for approximate incidences and their application to the camera posing problem. (English) Zbl 07559208

Barequet, Gill (ed.) et al., 35th international symposium on computational geometry, SoCG 2019, Portland, Oregon, USA, June 18–21, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 129, Article 8, 14 p. (2019).
MSC:  68U05
PDFBibTeX XMLCite
Full Text: DOI arXiv

Stabbing pairwise intersecting disks by five points. (English) Zbl 1535.52003

Hsu, Wen-Lian (ed.) et al., 29th international symposium on algorithms and computation, ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 123, Article 50, 12 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI

Approximate minimum-weight matching with outliers under translation. (English) Zbl 1533.68399

Hsu, Wen-Lian (ed.) et al., 29th international symposium on algorithms and computation, ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 123, Article 26, 13 p. (2018).
MSC:  68W25 68U05
PDFBibTeX XMLCite
Full Text: DOI arXiv

Union of hypercubes and 3D Minkowski sums with random sizes. (English) Zbl 1502.52020

Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 10, 15 p. (2018).
MSC:  52C45 52B10 68U05
PDFBibTeX XMLCite
Full Text: DOI

Algebraic techniques in geometry. The 10th anniversary. (English) Zbl 1460.52020

Arreche, Carlos (ed.), Proceedings of the 43rd international symposium on symbolic and algebraic computation, ISSAC 2018, New York, NY, USA, July 16–19, 2018. New York, NY: Association for Computing Machinery (ACM). 1-5 (2018).
MSC:  52C10 68U05
PDFBibTeX XMLCite
Full Text: DOI

Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time. (English) Zbl 1403.68162

Czumaj, Artur (ed.), Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7–10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-503-1/ebook). 495-514 (2018).
MSC:  68R10 05C10 68U05
PDFBibTeX XMLCite
Full Text: arXiv Link

Dominance product and high-dimensional closest pair under \(L_\infty\). (English) Zbl 1457.68291

Okamoto, Yoshio (ed.) et al., 28th international symposium on algorithms and computation, ISAAC 2017, December 9–12, 2017, Phuket, Thailand. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 92, Article 39, 12 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points. (English) Zbl 1442.68252

Pruhs, Kirk (ed.) et al., 25th European symposium on algorithms, ESA 2017, Vienna, Austria, September 4–6, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 87, Article 52, 13 p. (2017).
MSC:  68U05 51M25 68W40
PDFBibTeX XMLCite
Full Text: DOI

Output sensitive algorithms for approximate incidences and their applications. (English) Zbl 1442.68247

Pruhs, Kirk (ed.) et al., 25th European symposium on algorithms, ESA 2017, Vienna, Austria, September 4–6, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 87, Article 5, 13 p. (2017).
MSC:  68U05 68W25
PDFBibTeX XMLCite
Full Text: DOI

Approximate nearest neighbor search amid higher-dimensional flats. (English) Zbl 1442.68246

Pruhs, Kirk (ed.) et al., 25th European symposium on algorithms, ESA 2017, Vienna, Austria, September 4–6, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 87, Article 4, 13 p. (2017).
MSC:  68U05 68P05 68W05
PDFBibTeX XMLCite
Full Text: DOI

Dynamic time warping and geometric edit distance: breaking the quadratic barrier. (English) Zbl 1441.68304

Chatzigiannakis, Ioannis (ed.) et al., 44th international colloquium on automata, languages, and programming, ICALP 2017, Warsaw, Poland July 10–14, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 80, Article 25, 14 p. (2017).
MSC:  68W40 68U05
PDFBibTeX XMLCite
Full Text: DOI

A nearly quadratic bound for the decision tree complexity of \(k\)-SUM. (English) Zbl 1432.68178

Aronov, Boris (ed.) et al., 33rd international symposium on computational geometry. SoCG 2017, Brisbane, Australia, July 4–7, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 77, Article 41, 15 p. (2017).
MSC:  68Q25 68P05 68U05
PDFBibTeX XMLCite
Full Text: DOI

Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications. (English) Zbl 1410.68370

Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2495-2504 (2017).
MSC:  68U05 68P05
PDFBibTeX XMLCite
Full Text: DOI

Eliminating depth cycles among triangles in three dimensions. (English) Zbl 1410.68362

Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2476-2494 (2017).
PDFBibTeX XMLCite
Full Text: DOI

Incidences with curves and surfaces in three dimensions, with applications to distinct and repeated distances. (English) Zbl 1417.52032

Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2456-2475 (2017).
MSC:  52C30 14Q20 52C10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Approximating the \(k\)-level in three-dimensional plane arrangements. (English) Zbl 1384.52022

Loebl, Martin (ed.) et al., A journey through discrete mathematics. A tribute to Jiří Matoušek. Cham: Springer (ISBN 978-3-319-44478-9/hbk; 978-3-319-44479-6/ebook). 467-503 (2017).
MSC:  52C35 51A05 51A20
PDFBibTeX XMLCite
Full Text: DOI arXiv

Algorithmic and geometric aspects of robotics. Reprint of the 1987 edition. (English) Zbl 1457.68008

Routledge Revivals. Boca Raton, FL: CRC Press (ISBN 978-1-138-20347-1/hbk; 978-1-138-20350-1/pbk; 978-1-315-47145-7/ebook). xii, 305 p. (2016).
PDFBibTeX XMLCite
Full Text: DOI

Approximating the \(k\)-level in three-dimensional plane arrangements. (English) Zbl 1411.68170

Krauthgamer, Robert (ed.), Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1193-1212 (2016).
MSC:  68U05 52C45 68W20
PDFBibTeX XMLCite
Full Text: DOI

Almost tight bounds for eliminating depth cycles in three dimensions. (English) Zbl 1375.68120

Wichs, Daniel (ed.) et al., Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC ’16, Cambridge, MA, USA, June 19–21, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4132-5). 1-8 (2016).
PDFBibTeX XMLCite
Full Text: DOI arXiv

The number of unit-area triangles in the plane: theme and variations. (English) Zbl 1382.52015

Arge, Lars (ed.) et al., 31st international symposium on computational geometry, SoCG’15, Eindhoven, Netherlands, June 22–25, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-83-5). LIPIcs – Leibniz International Proceedings in Informatics 34, 569-583 (2015).
MSC:  52C10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Incidences between points and lines in three dimensions. (English) Zbl 1382.52016

Arge, Lars (ed.) et al., 31st international symposium on computational geometry, SoCG’15, Eindhoven, Netherlands, June 22–25, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-83-5). LIPIcs – Leibniz International Proceedings in Informatics 34, 553-568 (2015).
MSC:  52C10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Polynomials vanishing on Cartesian products: the Elekes-Szabó theorem revisited. (English) Zbl 1380.05011

Arge, Lars (ed.) et al., 31st international symposium on computational geometry, SoCG’15, Eindhoven, Netherlands, June 22–25, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-83-5). LIPIcs – Leibniz International Proceedings in Informatics 34, 522-536 (2015).
PDFBibTeX XMLCite
Full Text: DOI

The discrete Fréchet distance with shortcuts via approximate distance counting and selection. (English) Zbl 1395.68290

Proceedings of the 30th annual symposium on computational geometry, SoCG ’14, Kyoto, Japan, June 8–11, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2594-3). 377-386 (2014).
MSC:  68U05 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Polynomials vanishing on grids: the Elekes-Rónyai problem revisited. (English) Zbl 1395.05007

Proceedings of the 30th annual symposium on computational geometry, SoCG ’14, Kyoto, Japan, June 8–11, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2594-3). 251-260 (2014).
MSC:  05A10 14P05 52C10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Finding the largest disk containing a query point in logarithmic time with linear storage (extended abstract). (English) Zbl 1395.68308

Proceedings of the 30th annual symposium on computational geometry, SoCG ’14, Kyoto, Japan, June 8–11, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2594-3). 206-213 (2014).
MSC:  68U05 68P05
PDFBibTeX XMLCite
Full Text: DOI

On triple intersections of three families of unit circles. (English) Zbl 1395.52020

Proceedings of the 30th annual symposium on computational geometry, SoCG ’14, Kyoto, Japan, June 8–11, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2594-3). 198-205 (2014).
MSC:  52C10 05A16
PDFBibTeX XMLCite
Full Text: DOI arXiv

Incidences between points and lines in \(\mathbb{R}^4\) (extended abstract). (English) Zbl 1395.51005

Proceedings of the 30th annual symposium on computational geometry, SoCG ’14, Kyoto, Japan, June 8–11, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2594-3). 189-197 (2014).
MSC:  51D20 14N10 52C10
PDFBibTeX XMLCite
Full Text: DOI

Minimum partial-matching and Hausdorff RMS-distance under translation: combinatorics and algorithms. (English) Zbl 1423.68538

Schulz, Andreas S. (ed.) et al., Algorithms – ESA 2014. 22nd annual European symposium, Wrocław, Poland, September 8–10, 2014. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8737, 100-111 (2014).
MSC:  68U05
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

Reporting neighbors in high-dimensional Euclidean space. (English) Zbl 1422.68235

Khanna, Sanjeev (ed.), Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, January 6–8, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 784-803 (2013).
MSC:  68U05 68W20 68W40
PDFBibTeX XMLCite
Full Text: DOI

Computing the discrete Fréchet distance in subquadratic time. (English) Zbl 1422.68233

Khanna, Sanjeev (ed.), Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, LA, USA, January 6–8, 2013. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 156-167 (2013).
MSC:  68U05 68Q45 68W40
PDFBibTeX XMLCite
Full Text: DOI arXiv

Union of random Minkowski sums and network vulnerability analysis. (English) Zbl 1305.68096

Proceedings of the 29th annual symposium on computational geometry, SoCG 2013, Rio de Janeiro, Brazil, June 17–20, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2031-3). 177-186 (2013).
PDFBibTeX XMLCite
Full Text: DOI Link

Improved bounds for incidences between points and circles. (English) Zbl 1305.68095

Proceedings of the 29th annual symposium on computational geometry, SoCG 2013, Rio de Janeiro, Brazil, June 17–20, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2031-3). 97-106 (2013).
MSC:  68Q17 68R05 68U05
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

Counting plane graphs: cross-graph charging schemes. (English) Zbl 1378.68185

Didimo, Walter (ed.) et al., Graph drawing. 20th international symposium, GD 2012, Redmond, WA, USA, September 19–21, 2012. Revised selected papers. Berlin: Springer (ISBN 978-3-642-36762-5/pbk). Lecture Notes in Computer Science 7704, 19-30 (2013).
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

Database

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

Biographic Reference