Jean Cardinal

Arturo Merino

Torsten Mütze

ACM Trans. Algorithms, January, 2025

Rectangulotopes.

[BibT_eX]

[DOI]

Vincent Pilaud

Eur. J. Comb., 2025

Shortest paths on polymatroids and hypergraphic polytopes.

[BibT_eX]

[DOI]

Raphael Steiner

Comb. Theory, 2025

Combinatorics of rectangulations: old and new bijections.

[BibT_eX]

[DOI]

Comb. Theory, 2025

Facet-Hamiltonicity.

[BibT_eX]

[DOI]

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

Hitting and Covering Affine Families of Convex Polyhedra, with Applications to Robust Optimization.

[BibT_eX]

[DOI]

Xavier Goaoc

Sarah Wajsbrot

Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, 2025

Compact Representation of Semilinear and Terrain-Like Graphs.

[BibT_eX]

[DOI]

Yelena Yuditsky

Proceedings of the 33rd Annual European Symposium on Algorithms, 2025

2024

The rotation distance of brooms.

[BibT_eX]

[DOI]

Lionel Pournin

Eur. J. Comb., 2024

Triangulations in Geometry and Topology (Dagstuhl Seminar 24072).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2024

The Existential Theory of the Reals as a Complexity Class: A Compendium.

[BibT_eX]

[DOI]

Marcus Schaefer

Tillmann Miltzow

CoRR, 2024

The Complexity of Intersection Graphs of Lines in Space and Circle Orders.

[BibT_eX]

[DOI]

CoRR, 2024

The expansion of half-integral polytopes.

[BibT_eX]

[DOI]

Lionel Pournin

CoRR, 2024

A General Technique for Searching in Implicit Sets via Function Inversion.

[BibT_eX]

[DOI]

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

2023

Colouring bottomless rectangles and arborescences.

[BibT_eX]

[DOI]

Comput. Geom., December, 2023

Combinatorial Generation via Permutation Languages. V. Acyclic Orientations.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., September, 2023

Zigzagging through acyclic orientations of chordal graphs and hypergraphs.

[BibT_eX]

[DOI]

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

Inapproximability of Shortest Paths on Perfect Matching Polytopes.

[BibT_eX]

[DOI]

Raphael Steiner

Proceedings of the Integer Programming and Combinatorial Optimization, 2023

Improved Algebraic Degeneracy Testing.

[BibT_eX]

[DOI]

Micha Sharir

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

Dynamic Schnyder woods.

[BibT_eX]

Proceedings of the 35th Canadian Conference on Computational Geometry, 2023

2022

Algorithms for approximate sparse regression and nearest induced hulls.

[BibT_eX]

[DOI]

J. Comput. Geom., 2022

Efficient generation of elimination trees and graph associahedra.

[BibT_eX]

[DOI]

Arturo Merino

Torsten Mütze

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

2021

Modular Subset Sum, Dynamic Strings, and Zero-Sum Sets.

[BibT_eX]

[DOI]

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Bounds on the Diameter of Graph Associahedra.

[BibT_eX]

[DOI]

Lionel Pournin

Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium, 2021

Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

Worst-Case Efficient Dynamic Geometric Independent Set.

[BibT_eX]

[DOI]

Grigorios Koumoutsos

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

An Instance-Optimal Algorithm for Bichromatic Rectangular Visibility.

[BibT_eX]

[DOI]

Justin Dallant

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

Approximability of (Simultaneous) Class Cover for Boxes.

[BibT_eX]

Justin Dallant

Proceedings of the 33rd Canadian Conference on Computational Geometry, 2021

2020

Dynamic Geometric Independent Set.

[BibT_eX]

[DOI]

CoRR, 2020

Solving and Sampling with Many Solutions.

[BibT_eX]

[DOI]

Jerri Nummenpalo

Emo Welzl

Algorithmica, 2020

Drawing Graphs as Spanners.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2020

Sparse Regression via Range Counting.

[BibT_eX]

[DOI]

Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory, 2020

Competitive Online Search Trees on Trees.

[BibT_eX]

[DOI]

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

Geometric Pattern Matching Reduces to k-SUM.

[BibT_eX]

[DOI]

Boris Aronov

Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

2019

Finding a Maximum-Weight Convex Set in a Chordal Graph.

[BibT_eX]

[DOI]

Jean-Paul Doignon

Keno Merckx

J. Graph Algorithms Appl., 2019

Subquadratic Algorithms for Algebraic 3SUM.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2019

Encoding 3SUM.

[BibT_eX]

[DOI]

CoRR, 2019

Information-theoretic lower bounds for quantum sorting.

[BibT_eX]

[DOI]

Jérémie Roland

CoRR, 2019

Flip Distances Between Graph Orientations.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2019

Chirotopes of Random Points in Space are Realizable on a Small Integer Grid.

[BibT_eX]

Ruy Fabila Monroy

Carlos Hidalgo-Toscano

Proceedings of the 31st Canadian Conference on Computational Geometry, 2019

Three-Coloring Three-Dimensional Uniform Hypergraphs.

[BibT_eX]

Proceedings of the 31st Canadian Conference on Computational Geometry, 2019

2018

A Note on Flips in Diagonal Rectangulations.

[BibT_eX]

[DOI]

Vera Sacristán

Rodrigo I. Silveira

Discret. Math. Theor. Comput. Sci., 2018

On the Diameter of Tree Associahedra.

[BibT_eX]

[DOI]

Pablo Pérez-Lantero

Electron. J. Comb., 2018

Subquadratic Encodings for Point Configurations.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Computational Geometry, 2018

Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 24th International Conference, 2018

2017

Intersection Graphs of Rays and Grounded Segments.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2017

Dynamic Graph Coloring.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 15th International Symposium, 2017

Solving and Sampling with Many Solutions: Satisfiability and Other Hard Problems.

[BibT_eX]

[DOI]

Jerri Nummenpalo

Emo Welzl

Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

Subquadratic Algorithms for Algebraic Generalizations of 3SUM.

[BibT_eX]

[DOI]

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

2016

Reconstructing Point Set Order Types from Radial Orderings.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2016

On the shelling antimatroids of split graphs.

[BibT_eX]

[DOI]

Keno Merckx

Jean-Paul Doignon

Electron. Notes Discret. Math., 2016

Ramsey-type theorems for lines in 3-space.

[BibT_eX]

[DOI]

Michael S. Payne

Noam Solomon

Discret. Math. Theor. Comput. Sci., 2016

Topological Drawings of Complete Bipartite Graphs.

[BibT_eX]

[DOI]

Stefan Felsner

Proceedings of the Graph Drawing and Network Visualization - 24th International Symposium, 2016

Solving k-SUM Using Few Linear Queries.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

Computational Geometry Column 62.

[BibT_eX]

[DOI]

SIGACT News, 2015

Cannibal Animal Games: a new variant of Tic-Tac-Toe.

[BibT_eX]

[DOI]

J. Inf. Process., 2015

The Complexity of Simultaneous Geometric Graph Embedding.

[BibT_eX]

[DOI]

Vincent Kusters

J. Graph Algorithms Appl., 2015

On the Decision Tree Complexity of $k$-SUM.

[BibT_eX]

[DOI]

CoRR, 2015

Hitting All Maximal Independent Sets of a Bipartite Graph.

[BibT_eX]

[DOI]

Algorithmica, 2015

Arc Diagrams, Flip Distances, and Hamiltonian Triangulations.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Recognition and Complexity of Point Visibility Graphs.

[BibT_eX]

[DOI]

Udo Hoffmann

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

2014

The Price of Connectivity for Vertex Cover.

[BibT_eX]

[DOI]

Discret. Math. Theor. Comput. Sci., 2014

Cell-Paths in Mono- and Bichromatic Line Arrangements in the Plane.

[BibT_eX]

[DOI]

Discret. Math. Theor. Comput. Sci., 2014

General Position Subsets and Independent Hyperplanes in d-Space.

[BibT_eX]

[DOI]

Csaba D. Tóth

David R. Wood

CoRR, 2014

Making Octants Colorful and Related Covering Decomposition Problems.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Reconstructing Point Set Order Typesfrom Radial Orderings.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 25th International Symposium, 2014

2013

Making Triangles Colorful.

[BibT_eX]

[DOI]

J. Comput. Geom., 2013

Coloring and Guarding Arrangements.

[BibT_eX]

[DOI]

Discret. Math. Theor. Comput. Sci., 2013

Non-crossing matchings of points with geometric objects.

[BibT_eX]

[DOI]

Comput. Geom., 2013

Coloring Hypergraphs Induced by Dynamic Point Sets and Bottomless Rectangles.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

Covering Partial Cubes with Zones.

[BibT_eX]

[DOI]

Stefan Felsner

Proceedings of the Discrete and Computational Geometry and Graphs, 2013

Cell-Paths in Mono- and Bichromatic Line Arrangements in the Plane.

[BibT_eX]

[DOI]

Proceedings of the 25th Canadian Conference on Computational Geometry, 2013

On Generalized Comparison-Based Sorting Problems.

[BibT_eX]

[DOI]

Proceedings of the Space-Efficient Data Structures, 2013

2012

Approximating vertex cover in dense hypergraphs.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2012

On Universal Point Sets for Planar Graphs.

[BibT_eX]

[DOI]

Michael Hoffmann

Vincent Kusters

Proceedings of the Computational Geometry and Graphs - Thailand-Japan Joint Conference, 2012

Coloring Planar Homothets and Three-Dimensional Hypergraphs.

[BibT_eX]

[DOI]

Matias Korman

Proceedings of the LATIN 2012: Theoretical Informatics, 2012

The Clique Problem in Ray Intersection Graphs.

[BibT_eX]

[DOI]

Sergio Cabello

Proceedings of the Algorithms - ESA 2012, 2012

The Price of Connectivity for Vertex Cover: Perfect, Near-Perfect and Critical Graphs.

[BibT_eX]

Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2012

2011

Algorithmic Folding Complexity.

[BibT_eX]

[DOI]

Graphs Comb., 2011

Approximating Subdense Instances of Covering Problems.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2011

Helly Numbers of Polyominoes.

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

2010

Non-cooperative facility location and covering games.

[BibT_eX]

[DOI]

Martin Hoefer

Theor. Comput. Sci., 2010

Minimum sum edge colorings of multicycles.

[BibT_eX]

[DOI]

Vlady Ravelomanana

Discret. Appl. Math., 2010

Highway hull revisited.

[BibT_eX]

[DOI]

Comput. Geom., 2010

Sorting under partial information (without the ellipsoid algorithm).

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Colorful Strips.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2010: Theoretical Informatics, 2010

Matching Points with Things.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2010: Theoretical Informatics, 2010

2009

Detecting all regular polygons in a point set

[BibT_eX]

[DOI]

CoRR, 2009

Empty region graphs.

[BibT_eX]

[DOI]

Comput. Geom., 2009

The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics, 5th International Workshop, 2009

An efficient algorithm for partial order production.

[BibT_eX]

[DOI]

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

Decomposition of multiple coverings into more parts.

[BibT_eX]

[DOI]

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

Algorithmic Folding Complexity.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Minimum Entropy Combinatorial Optimization Problems.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Theory and Computational Practice, 2009

Relaxed Gabriel Graphs.

[BibT_eX]

[DOI]

Proceedings of the 21st Annual Canadian Conference on Computational Geometry, 2009

2008

Minimum entropy orientations.

[BibT_eX]

[DOI]

Oper. Res. Lett., 2008

Chromatic Edge Strength of Some Multigraphs.

[BibT_eX]

[DOI]

Vlady Ravelomanana

Electron. Notes Discret. Math., 2008

Set Covering Problems with General Objective Functions

[BibT_eX]

[DOI]

Christophe Dumeunier

CoRR, 2008

Optimal location of transportation devices.

[BibT_eX]

[DOI]

Comput. Geom., 2008

Coloring Geometric Range Spaces.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2008: Theoretical Informatics, 2008

Draining a Polygon - or - Rolling a Ball out of a Polygon.

[BibT_eX]

Proceedings of the 20th Annual Canadian Conference on Computational Geometry, 2008

Connected Vertex Covers in Dense Graphs.

[BibT_eX]

[DOI]

Eythan Levy

Proceedings of the Approximation, 2008

2007

Efficient Rate-Distortion Optimized Media Streaming for Tree-Structured Packet Dependencies.

[BibT_eX]

[DOI]

IEEE Trans. Multim., 2007

Moving Walkways, Escalators, and Elevators

[BibT_eX]

[DOI]

CoRR, 2007

The Stackelberg Minimum Spanning Tree Game.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007

2006

Branch and bound algorithms for rate-distortion optimized media streaming.

[BibT_eX]

[DOI]

IEEE Trans. Multim., 2006

Juggling with Pattern Matching.

[BibT_eX]

[DOI]

Steve Kremer

Theory Comput. Syst., 2006

Selfish Service Installation in Networks.

[BibT_eX]

[DOI]

Martin Hoefer

Proceedings of the Internet and Network Economics, Second International Workshop, 2006

Improved Approximation Bounds for Edge Dominating Set in Dense Graphs.

[BibT_eX]

[DOI]

Eythan Levy

Proceedings of the Approximation and Online Algorithms, 4th International Workshop, 2006

Constructing Dependency Trees for Rate-Distortion Optimized Media Streaming.

[BibT_eX]

[DOI]

Proceedings of the 2006 IEEE International Conference on Acoustics Speech and Signal Processing, 2006

LUMINESStrategies.

[BibT_eX]

[DOI]

Proceedings of the Computers and Games, 5th International Conference, 2006

Tight Results on Minimum Entropy Set Cover.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2006

2005

Minimum Entropy Coloring.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

Dynamic programming algorithm for rate-distortion optimized media streaming.

[BibT_eX]

[DOI]

Proceedings of the 2005 International Conference on Image Processing, 2005

Region counting graphs.

[BibT_eX]

[DOI]

Proceedings of the (Informal) Proceedings of the 21st European Workshop on Computational Geometry, 2005

A Tight Analysis of the Maximal Matching Heuristic.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

Pricing of Geometric Transportation Networks.

[BibT_eX]

[DOI]

Proceedings of the 17th Canadian Conference on Computational Geometry, 2005

Region Counting Distances and Region Counting Circles.

[BibT_eX]

[DOI]

Proceedings of the 17th Canadian Conference on Computational Geometry, 2005

2004

Entropy-constrained index assignments for multiple description quantizers.

[BibT_eX]

[DOI]

IEEE Trans. Signal Process., 2004

Reconciliation of a quantum-distributed Gaussian key.

[BibT_eX]

[DOI]

Gilles Van Assche

Nicolas J. Cerf

IEEE Trans. Inf. Theory, 2004

Designing Small Keyboards Is Hard.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

On minimum entropy graph colorings.

[BibT_eX]

[DOI]

Gilles Van Assche

Proceedings of the 2004 IEEE International Symposium on Information Theory, 2004

On the Complexity of Rate-Distortion Optimal Streaming of Packetized Media.

[BibT_eX]

[DOI]

Proceedings of the 2004 Data Compression Conference (DCC 2004), 2004

Local properties of geometric graphs.

[BibT_eX]

[DOI]

Proceedings of the 16th Canadian Conference on Computational Geometry, 2004

Lazy Algorithms for Dynamic Closest Pair with Arbitary Distance Measures.

[BibT_eX]

David Eppstein

Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, 2004

2003

Tree-Structured Multiple Description Coding.

[BibT_eX]

[DOI]

J. VLSI Signal Process., 2003

Construction of a shared secret key using continuous variables.

[BibT_eX]

[DOI]

Gilles Van Assche

Proceedings of the Proceedings 2003 IEEE Information Theory Workshop, 2003

Compression of side information.

[BibT_eX]

[DOI]

Proceedings of the 2003 IEEE International Conference on Multimedia and Expo, 2003

Multistage index assignments for M-description coding.

[BibT_eX]

[DOI]

Proceedings of the 2003 International Conference on Image Processing, 2003

2002

Complexity-constrained tree-structured vector quantizers.

[BibT_eX]

[DOI]

Signal Process., 2002

Local optimization of index assignments for multiple description coding.

[BibT_eX]

[DOI]

Sourour Elloumi

Martine Labbé

Proceedings of the 11th European Signal Processing Conference, 2002

2001

Fast fractal compression of greyscale images.

[BibT_eX]

[DOI]

IEEE Trans. Image Process., 2001

Design of asymmetric tree-structured multiple description source codes.

[BibT_eX]

[DOI]

Proceedings of the Fourth IEEE Workshop on Multimedia Signal Processing, 2001

Design of Tree-Structured Multiple Description Vector Quantizers.

[BibT_eX]

[DOI]

Proceedings of the Data Compression Conference, 2001

2000

A Lagrangian optimization approach to complexity-constrained TSVQ.

[BibT_eX]

[DOI]

IEEE Signal Process. Lett., 2000

Multipath tree-structured vector quantizers.

[BibT_eX]

[DOI]

Proceedings of the 10th European Signal Processing Conference, 2000

Tree-Based Search for ECVQ.

[BibT_eX]

[DOI]

Proceedings of the Data Compression Conference, 2000

1999

Fast Search for Entropy-Constrained VQ.

[BibT_eX]

[DOI]