×

Found 154 Documents (Results 1–100)

On the number of incidences when avoiding an induced biclique in geometric settings. (English) Zbl 07848010

Bansal, Nikhil (ed.) et al., Proceedings of the 34th annual ACM-SIAM symposium on discrete algorithms, SODA 2023, Florence, Italy, January 22–25, 2023. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1398-1413 (2023).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Approximation algorithms for maximum matchings in geometric intersection graphs. (English) Zbl 07849045

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 47, 13 p. (2022).
MSC:  68U05
PDFBibTeX XMLCite
Full Text: DOI arXiv

Fast algorithms for geometric consensuses. (English) Zbl 07760179

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 50, 16 p. (2020).
MSC:  68U05
PDFBibTeX XMLCite
Full Text: DOI

Fast LP-based approximations for geometric packing and covering problems. (English) Zbl 07304085

Chawla, Shuchi (ed.), Proceedings of the 31st annual ACM-SIAM symposium on discrete algorithms, SODA 2020, Salt Lake City, UT, USA, January 5–8, 2020. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1019-1038 (2020).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Journey to the center of the point set. (English) Zbl 07559241

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 41, 14 p. (2019).
MSC:  68U05
PDFBibTeX XMLCite
Full Text: DOI

Smallest \(k\)-enclosing rectangle revisited. (English) Zbl 07559223

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 23, 15 p. (2019).
MSC:  68U05
PDFBibTeX XMLCite
Full Text: DOI

A spanner for the day after. (English) Zbl 07559219

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 19, 15 p. (2019).
MSC:  68U05
PDFBibTeX XMLCite
Full Text: DOI

On locality-sensitive orderings and their applications. (English) Zbl 07559064

Blum, Avrim (ed.), 10th innovations in theoretical computer science conference, ITCS 2019, January 10–12, 2019, San Diego, CA, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 124, Article 21, 17 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

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

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 sparse linear regression. (English) Zbl 1499.68369

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 77, 14 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Grid peeling and the affine curve-shortening flow. (English) Zbl 1430.68368

Pagh, Rasmus (ed.) et al., Proceedings of the 20th workshop on algorithm engineering and experiments, ALENEX ’18, New Orleans, LA, January 7–8, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 109-116 (2018).
MSC:  68U05 52C05
PDFBibTeX XMLCite
Full Text: DOI arXiv

On separating points by lines. (English) Zbl 1403.68317

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). 918-932 (2018).
MSC:  68U05 68W25
PDFBibTeX XMLCite
Full Text: Link

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

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

Sparse approximation via generating point sets. (English) Zbl 1411.68165

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). 548-557 (2016).
MSC:  68U05 52B55 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Separating a Voronoi diagram via local search. (English) Zbl 1387.68240

Fekete, Sándor (ed.) et al., 32nd international symposium on computational geometry, SoCG’16, Boston, MA, USA, June 14–17, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-009-5). LIPIcs – Leibniz International Proceedings in Informatics 51, Article 18, 16 p. (2016).
MSC:  68U05 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

From proximity to utility: a Voronoi partition of Pareto optima. (English) Zbl 1378.68166

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, 689-703 (2015).
MSC:  68U05 91B32
PDFBibTeX XMLCite
Full Text: DOI

Space exploration via proximity search. (English) Zbl 1378.68173

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, 374-389 (2015).
MSC:  68U05
PDFBibTeX XMLCite
Full Text: DOI

Shortest path in a polygon using sublinear space. (English) Zbl 1378.68172

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, 111-125 (2015).
MSC:  68U05 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Approximation algorithms for polynomial-expansion and low-density graphs. (English) Zbl 1466.68059

Bansal, Nikhil (ed.) et al., Algorithms – ESA 2015. 23rd annual European symposium, Patras, Greece, September 14–16, 2015. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 9294, 717-728 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the complexity of randomly weighted Voronoi diagrams. (English) Zbl 1401.68350

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). 232-241 (2014).
MSC:  68U05 52C45
PDFBibTeX XMLCite
Full Text: DOI arXiv

Quasi-polynomial time approximation scheme for sparse subsets of polygons. (English) Zbl 1395.68306

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). 120-129 (2014).
MSC:  68U05 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Robust proximity search for balls using sublinear space. (English) Zbl 1360.68876

Raman, Venkatesh (ed.) et al., 34th international conference on foundation of software technology and theoretical computer science, FSTTCS 2014, New Delhi, India, December 15–17, 2014. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-77-4). LIPIcs – Leibniz International Proceedings in Informatics 29, 315-326 (2014).
MSC:  68U05 68P05
PDFBibTeX XMLCite
Full Text: DOI

Approximating the maximum overlap of polygons under translation. (English) Zbl 1359.68283

Schulz, Andreas S. (ed.) et al., Algorithms – ESA 2014. 22nd annual European symposium, Wrocław, Poland, September 8–10, 2014. Proceedings. Berlin: Springer (ISBN 978-3-662-44776-5/pbk). Lecture Notes in Computer Science 8737, 542-553 (2014).
MSC:  68U05 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Convex hulls under uncertainty. (English) Zbl 1370.68291

Schulz, Andreas S. (ed.) et al., Algorithms – ESA 2014. 22nd annual European symposium, Wrocław, Poland, September 8–10, 2014. Proceedings. Berlin: Springer (ISBN 978-3-662-44776-5/pbk). Lecture Notes in Computer Science 8737, 37-48 (2014).
MSC:  68U05 52B55
PDFBibTeX XMLCite
Full Text: DOI arXiv

Euclidean spanners in high dimensions. (English) Zbl 1421.68176

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). 804-809 (2013).
MSC:  68U05
PDFBibTeX XMLCite
Full Text: DOI

Net and prune: a linear time algorithm for Euclidean distance problems. (English) Zbl 1293.68167

Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 605-614 (2013).
MSC:  68Q25 68W25 68U05
PDFBibTeX XMLCite
Full Text: DOI

Jaywalking your dog: computing the Fréchet distance with shortcuts. (English) Zbl 1421.68170

Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 318-337 (2012).
PDFBibTeX XMLCite
Full Text: Link

How to walk your dog in the mountains with no magic leash. (English) Zbl 1293.68290

Proceedings of the 28th annual symposium on computational geometry, SoCG 2012, Chapel Hill, NC, USA, June 17–20, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1299-8). 121-130 (2012).
MSC:  68U05 68Q25 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the expected complexity of Voronoi diagrams on terrains. (English) Zbl 1293.68287

Proceedings of the 28th annual symposium on computational geometry, SoCG 2012, Chapel Hill, NC, USA, June 17–20, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1299-8). 101-110 (2012).
MSC:  68U05 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Geometric packing under non-uniform constraints. (English) Zbl 1293.05243

Proceedings of the 28th annual symposium on computational geometry, SoCG 2012, Chapel Hill, NC, USA, June 17–20, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1299-8). 11-20 (2012).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Minimum convex partitions and maximum empty polytopes. (English) Zbl 1357.68292

Fomin, Fedor V. (ed.) et al., Algorithm theory – SWAT 2012. 13th Scandinavian symposium and workshops, Helsinki, Finland, July 4–6, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-31154-3/pbk). Lecture Notes in Computer Science 7357, 213-224 (2012).
PDFBibTeX XMLCite
Full Text: DOI arXiv

The frechet distance revisited and extended. (English) Zbl 1283.68365

Proceedings of the 27th annual symposium on computational geometry, SoCG 2011, Paris, France, June 13–15, 2011. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0682-9). 448-457 (2011).
MSC:  68U05 65D18 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Computing the Fréchet distance between folded polygons. (English) Zbl 1342.68332

Dehne, Frank (ed.) et al., Algorithms and data structures. 12th international symposium, WADS 2011, New York, NY, USA, August 15–17, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22299-3/pbk). Lecture Notes in Computer Science 6844, 267-278 (2011).
MSC:  68U05 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Approximating the Fréchet distance for realistic curves in near linear time. (English) Zbl 1284.68295

Proceedings of the 26th annual symposium on computational geometry, SoCG 2010, Snowbird, UT, USA, June 13–16, 2010. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0016-2). 365-374 (2010).
PDFBibTeX XMLCite
Full Text: DOI arXiv

New constructions of SSPDs and their applications. (English) Zbl 1284.68570

Proceedings of the 26th annual symposium on computational geometry, SoCG 2010, Snowbird, UT, USA, June 13–16, 2010. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0016-2). 192-200 (2010).
MSC:  68U05 51M15
PDFBibTeX XMLCite
Full Text: DOI

On the set multi-cover problem in geometric settings. (English) Zbl 1388.68286

Proceedings of the 25th annual symposium on computational geometry, SCG 2009, Aarhus, Denmark, June 8–10, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-501-7). 341-350 (2009).
MSC:  68U05
PDFBibTeX XMLCite
Full Text: DOI

Approximation algorithms for maximum independent set of pseudo-disks. (English) Zbl 1388.68285

Proceedings of the 25th annual symposium on computational geometry, SCG 2009, Aarhus, Denmark, June 8–10, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-501-7). 333-340 (2009).
MSC:  68U05 68R10 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Robust shape fitting via peeling and grating coresets. Reprinted from the journal Discrete & Computational Geometry 39, No. 1-3 (2008). (English) Zbl 1171.68777

Goodman, Jacob E. (ed.) et al., Twentieth anniversary volume: Discrete and computational geometry. New York, NY: Springer (ISBN 978-0-387-87362-6/pbk). 36-56 (2009).
MSC:  68U05 68W25
PDFBibTeX XMLCite

Embeddings of surfaces, curves, and moving points in Euclidean space. (English) Zbl 1221.51025

Proceedings of the 23rd annual symposium on computational geometry 2007, Gyeongiu, South Korea, June 6–8, 2007. New York, NY: Association for Computing Machinery (ISBN 978-1-59593-705-6). 381-389 (2007).
MSC:  51M05 65D18 68U05
PDFBibTeX XMLCite
Full Text: DOI

On approximate halfspace range counting and relative epsilon-approximations. (English) Zbl 1221.51026

Proceedings of the 23rd annual symposium on computational geometry 2007, Gyeongiu, South Korea, June 6–8, 2007. New York, NY: Association for Computing Machinery (ISBN 978-1-59593-705-6). 327-336 (2007).
PDFBibTeX XMLCite
Full Text: DOI

Robust shape fitting via peeling and grating coresets. (English) Zbl 1192.68723

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, January 22–24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-605-5). 182-191 (2006).
MSC:  68U05
PDFBibTeX XMLCite
Full Text: DOI

How to get close to the median shape. (English) Zbl 1153.68533

Computational geometry (SCG’06). Proceedings of the twenty-second annual symposium on computational geometry 2006, Sedona, Arizona, USA, June, 05–07, 2006. New York, NY: Association for Computing Machinery (ISBN 1-59593-340-9). 402-410 (2006).
MSC:  68U05 65D17
PDFBibTeX XMLCite

The orienteering problem in the plane revisited. (English) Zbl 1153.65319

Computational geometry (SCG’06). Proceedings of the twenty-second annual symposium on computational geometry 2006, Sedona, Arizona, USA, June, 05–07, 2006. New York, NY: Association for Computing Machinery (ISBN 1-59593-340-9). 247-254 (2006).
MSC:  65D18 68U05
PDFBibTeX XMLCite

Coresets for discrete integration and clustering. (English) Zbl 1177.68238

Arun-Kumar, S. (ed.) et al., FSTTCS 2006: Foundations of software technology and theoretical computer science. 26th international conference, Kolkata, India, December 13–15, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-49994-7/pbk). Lecture Notes in Computer Science 4337, 33-44 (2006).
MSC:  68U05 65D30
PDFBibTeX XMLCite
Full Text: DOI

Fréchet distance for curves, revisited. (English) Zbl 1131.68561

Azar, Yossi (ed.) et al., Algorithms – ESA 2006. 14th annual European symposium, Zurich, Switzerland, September 11–13, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-38875-3/pbk). Lecture Notes in Computer Science 4168, 52-63 (2006).
MSC:  68U05 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Filter Results by …

Document Type

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software