Matthew J. Katz

According to our database, Matthew J. Katz authored at least 133 papers between 1989 and 2025.

Collaborative distances:

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

2025

Spanners under the Hausdorff and Fréchet distances.

Tsuri Farhana, Matthew J. Katz

Inf. Process. Lett., 2025

2024

On reverse shortest paths in geometric proximity graphs.

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

Comput. Geom., February, 2024

Discrete Fr\'echet Distance Oracles.

Boris Aronov, Tsuri Farhana, Matthew J. Katz, Indu Ramesh

CoRR, 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

Robustly Guarding Polygons.

Rathish Das, Omrit Filtser, Matthew J. Katz, Joseph S. B. Mitchell

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

Discrete Fréchet Distance Oracles.

Boris Aronov, Tsuri Farhana, Matthew J. Katz, Indu Ramesh

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

2023

Stabbing Pairwise Intersecting Disks by Four Points.

Paz Carmi, Matthew J. Katz, Pat Morin

Discret. Comput. Geom., December, 2023

Bottleneck matching in the plane.

Matthew J. Katz, Micha Sharir

Comput. Geom., June, 2023

Approximate Nearest Neighbor for Curves: Simple, Efficient, and Deterministic.

Arnold Filtser, Omrit Filtser, Matthew J. Katz

Algorithmica, May, 2023

A 4-approximation of the 2π3-MST.

Stav Ashur, Matthew J. Katz

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

Minimum-Link C-Oriented Paths Visiting a Sequence of Regions in the Plane.

Kerem Geva, Matthew J. Katz, Joseph S. B. Mitchell, Eli Packer

Proceedings of the Algorithms and Complexity - 13th International Conference, 2023

2022

Bipartite Diameter and Other Measures Under Translation.

Boris Aronov, Omrit Filtser, Matthew J. Katz, Khadijeh Sheikhan

Discret. Comput. Geom., 2022

Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains.

Stav Ashur, Omrit Filtser, Matthew J. Katz, Rachel Saban

Comput. Geom., 2022

Dynamic Approximate Multiplicatively-Weighted Nearest Neighbors.

Boris Aronov, Matthew J. Katz

Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory, 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

Minimizing total interference in asymmetric sensor networks.

A. Karim Abu-Affash, Paz Carmi, Matthew J. Katz

Theor. Comput. Sci., 2021

A constant-factor approximation algorithm for vertex guarding a WV-polygon.

Stav Ashur, Omrit Filtser, Matthew J. Katz

J. Comput. Geom., 2021

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

Matthew J. Katz, Micha Sharir

CoRR, 2021

Improved PTASs for convex barrier coverage.

Paz Carmi, Matthew J. Katz, Rachel Saban, Yael Stein

Comput. Geom., 2021

A 4-Approximation of the $\frac{2\pi }{3}$-MST.

Stav Ashur, Matthew J. Katz

Proceedings of the Algorithms and Data Structures - 17th International Symposium, 2021

2020

Resolving SINR Queries in a Dynamic Setting.

Boris Aronov, Gali Bar-On, Matthew J. Katz

SIAM J. Comput., 2020

Algorithms for the discrete Fréchet distance under translation.

Omrit Filtser, Matthew J. Katz

J. Comput. Geom., 2020

Tracking Paths.

Aritra Banik, Matthew J. Katz, Eli Packer, Marina Simakov

Discret. Appl. Math., 2020

A 4-Approximation of the $\frac{2π}{3}$-MST.

Stav Ashur, Matthew J. Katz

CoRR, 2020

Balanced line separators of unit disk graphs.

Paz Carmi, Man-Kwun Chiu, Matthew J. Katz, Matias Korman, Yoshio Okamoto, André van Renssen, Marcel Roeloffzen, Taichi Shiitada, Shakhar Smorodinsky

Comput. Geom., 2020

Sensor Network Topology Design and Analysis for Efficient Data Gathering by a Mobile Mule.

Harel Yedidsion, Stav Ashur, Aritra Banik, Paz Carmi, Matthew J. Katz, Michael Segal

Algorithmica, 2020

Dynamic Time Warping-Based Proximity Problems.

Boris Aronov, Matthew J. Katz, Elad Sulami

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

2019

Guest Editors' Foreword.

Boris Aronov, Matthew J. Katz

Discret. Comput. Geom., 2019

Locating battery charging stations to facilitate almost shortest paths.

Esther M. Arkin, Paz Carmi, Matthew J. Katz, Joseph S. B. Mitchell, Michael Segal

Discret. Appl. Math., 2019

Bottleneck detour tree of points on a path.

Greg Aloupis, Paz Carmi, Lilach Chaitman-Yerushalmi, Matthew J. Katz, Stefan Langerman

Comput. Geom., 2019

Efficient Nearest-Neighbor Query and Clustering of Planar Curves.

Boris Aronov, Omrit Filtser, Michael Horton, Matthew J. Katz, Khadijeh Sheikhan

Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

2018

Batched Point Location in SINR Diagrams via Algebraic Tools.

Boris Aronov, Matthew J. Katz

ACM Trans. Algorithms, 2018

Selecting and covering colored points.

Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Matthew J. Katz, Joseph S. B. Mitchell, Marina Simakov

Discret. Appl. Math., 2018

A PTAS for vertex guarding weakly-visible polygons - An extended abstract.

Matthew J. Katz

CoRR, 2018

Geometric Problems and Structures Arising from the Study of Wireless Networks.

Matthew J. Katz

Proceedings of the 30th Canadian Conference on Computational Geometry, 2018

2017

On interference among moving sensors and related problems.

Jean-Lou De Carufel, Matthew J. Katz, Matias Korman, André van Renssen, Marcel Roeloffzen, Shakhar Smorodinsky

J. Comput. Geom., 2017

Bounded-Angle Spanning Tree: Modeling Networks with Angular Constraints.

Rom Aschner, Matthew J. Katz

Algorithmica, 2017

Efficient data retrieval in faulty sensor networks using a mobile mule.

Harel Yedidsion, Aritra Banik, Paz Carmi, Matthew J. Katz, Michael Segal

Proceedings of the 15th International Symposium on Modeling and Optimization in Mobile, 2017

Network Optimization on Partitioned Pairs of Points.

Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Su Jia, Matthew J. Katz, Tyler Mayer, Joseph S. B. Mitchell

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

2016

On the General Chain Pair Simplification Problem.

Chenglin Fan, Omrit Filtser, Matthew J. Katz, Binhai Zhu

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 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

Bottleneck Steiner tree with bounded number of Steiner vertices.

A. Karim Abu-Affash, Paz Carmi, Matthew J. Katz

J. Discrete Algorithms, 2015

The Discrete Fréchet Gap.

Omrit Filtser, Matthew J. Katz

CoRR, 2015

On Kinetic Range Spaces and their Applications.

Jean-Lou De Carufel, Matya Katz, Matias Korman, André van Renssen, Marcel Roeloffzen, Shakhar Smorodinsky

CoRR, 2015

Spiderman graph: Visibility in urban regions.

Paz Carmi, Eran Friedman, Matthew J. Katz

Comput. Geom., 2015

On the Chain Pair Simplification Problem.

Chenglin Fan, Omrit Filtser, Matthew J. Katz, Tim Wylie, Binhai Zhu

Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

Choice Is Hard.

Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Matthew J. Katz, Joseph S. B. Mitchell, Marina Simakov

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Bottleneck Segment Matching.

Aritra Banik, Matthew J. Katz, Marina Simakov

Proceedings of the 27th Canadian Conference on Computational Geometry, 2015

Conflict-free Covering.

Esther M. Arkin, Aritra Banik, Paz Carmi, Gui Citovsky, Matthew J. Katz, Joseph S. B. Mitchell, Marina Simakov

Proceedings of the 27th Canadian Conference on Computational Geometry, 2015

2014

The Euclidean Bottleneck Steiner Path Problem and Other Applications of (α, β)-Pair Decomposition.

A. Karim Abu-Affash, Paz Carmi, Matthew J. Katz, Michael Segal

Discret. Comput. Geom., 2014

On the Chain Pair Simplification Problem.

Omrit Filtser, Matthew J. Katz, Tim Wylie, Binhai Zhu

CoRR, 2014

Bottleneck non-crossing matching in the plane.

A. Karim Abu-Affash, Paz Carmi, Matthew J. Katz, Yohai Trabelsi

Comput. Geom., 2014

Switching to Directional Antennas with Constant Increase in Radius and Hop Distance.

Prosenjit Bose, Paz Carmi, Mirela Damian, Robin Y. Flatland, Matthew J. Katz, Anil Maheshwari

Algorithmica, 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

Exploiting Geometry in the SINR _k Model.

Rom Aschner, Gui Citovsky, Matthew J. Katz

Proceedings of the Algorithms for Sensor Systems, 2014

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

Stable Roommates Spanner.

Prosenjit Bose, Paz Carmi, Lilach Chaitman-Yerushalmi, Sébastien Collette, Matthew J. Katz, Stefan Langerman

Comput. Geom., 2013

Symmetric connectivity with directional antennas.

Rom Aschner, Matthew J. Katz, Gila Morgenstern

Comput. Geom., 2013

Approximation Schemes for Covering and Packing.

Rom Aschner, Matthew J. Katz, Gila Morgenstern, Yelena Yuditsky

Proceedings of the WALCOM: Algorithms and Computation, 7th International Workshop, 2013

2012

Polychromatic 4-coloring of cubic bipartite plane graphs.

Elad Horev, Matthew J. Katz, Roi Krakovski, Atsuhiro Nakamoto

Discret. Math., 2012

Conflict-Free Coloring of points on a line with respect to a set of intervals.

Matthew J. Katz, Nissan Lev-Tov, Gila Morgenstern

Comput. Geom., 2012

The MST of symmetric disk graphs is light.

A. Karim Abu-Affash, Rom Aschner, Paz Carmi, Matthew J. Katz

Comput. Geom., 2012

A Scheme for Computing Minimum Covers within Simple Regions.

Matthew J. Katz, Gila Morgenstern

Algorithmica, 2012

Do Directional Antennas Facilitate in Reducing Interferences?

Rom Aschner, Matthew J. Katz, Gila Morgenstern

Proceedings of the Algorithm Theory - SWAT 2012, 2012

2011

Minimum power energy spanners in wireless ad hoc networks.

A. Karim Abu-Affash, Rom Aschner, Paz Carmi, Matthew J. Katz

Wirel. Networks, 2011

Optimal Cover of Points by Disks in a Simple Polygon.

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

SIAM J. Comput., 2011

Settling the bound on the rectilinear link radius of a simple rectilinear polygon.

Matthew J. Katz, Gila Morgenstern

Inf. Process. Lett., 2011

Guarding Orthogonal Art Galleries with Sliding Cameras.

Matthew J. Katz, Gila Morgenstern

Int. J. Comput. Geom. Appl., 2011

Multi Cover of a Polygon Minimizing the Sum of Areas.

A. Karim Abu-Affash, Paz Carmi, Matthew J. Katz, Gila Morgenstern

Int. J. Comput. Geom. Appl., 2011

Connectivity guarantees for wireless networks with directional antennas.

Paz Carmi, Matthew J. Katz, Zvi Lotker, Adi Rosén

Comput. Geom., 2011

The euclidean bottleneck steiner path problem.

A. Karim Abu-Affash, Paz Carmi, Matthew J. Katz, Michael Segal

Proceedings of the 27th ACM Symposium on Computational Geometry, 2011

2010

Direction assignment in wireless networks.

Boaz Ben-Moshe, Paz Carmi, Lilach Chaitman, Matthew J. Katz, Gila Morgenstern, Yael Stein

Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, 2010

2009

Polychromatic 4-coloring of guillotine subdivisions.

Elad Horev, Matthew J. Katz, Roi Krakovski, Maarten Löffler

Inf. Process. Lett., 2009

Improved bounds on the average distance to the Fermat-Weber center of a convex object.

A. Karim Abu-Affash, Matthew J. Katz

Inf. Process. Lett., 2009

Guarding Rectangular Partitions.

Yefim Dinitz, Matthew J. Katz, Roi Krakovski

Int. J. Comput. Geom. Appl., 2009

Minimum-Cost Load-Balancing Partitions.

Boris Aronov, Paz Carmi, Matthew J. Katz

Algorithmica, 2009

2008

Approximating the Visible Region of a Point on a Terrain.

Boaz Ben-Moshe, Paz Carmi, Matthew J. Katz

GeoInformatica, 2008

On guarding the vertices of rectilinear domains.

Matthew J. Katz, Gabriel S. Roisman

Comput. Geom., 2008

Polynomial-time approximation schemes for piercing and covering with applications in wireless networks.

Paz Carmi, Matthew J. Katz, Nissan Lev-Tov

Comput. Geom., 2008

2007

A Constant-Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding.

Boaz Ben-Moshe, Matthew J. Katz, Joseph S. B. Mitchell

SIAM J. Comput., 2007

Power Assignment in Radio Networks with Two Power Levels.

Paz Carmi, Matthew J. Katz

Algorithmica, 2007

Fault-Tolerant Power Assignment and Backbone in Wireless Networks.

Paz Carmi, Matthew J. Katz, Michael Segal, Hanan Shpungin

Ad Hoc Sens. Wirel. Networks, 2007

Covering Points by Unit Disks of Fixed Location.

Paz Carmi, Matthew J. Katz, Nissan Lev-Tov

Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

Distance Preserving Terrain Simplification - An Experimental Study.

Boaz Ben-Moshe, Matthew J. Katz, Igor Zaslavsky

Proceedings of the 19th Annual Canadian Conference on Computational Geometry, 2007

2006

The minimum-area spanning tree problem.

Paz Carmi, Matthew J. Katz, Joseph S. B. Mitchell

Comput. Geom., 2006

On Guarding Rectilinear Domains.

Matthew J. Katz, Gabriel S. Roisman

Proceedings of the Algorithm Theory, 2006

Finding large sticks and potatoes in polygons.

Olaf A. Hall-Holt, Matthew J. Katz, Piyush Kumar, Joseph S. B. Mitchell, Arik Sityon

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

2005

TSP with neighborhoods of varying size.

Mark de Berg, Joachim Gudmundsson, Matthew J. Katz, Christos Levcopoulos, Mark H. Overmars, A. Frank van der Stappen

J. Algorithms, 2005

Orthogonal segment stabbing.

Matthew J. Katz, Joseph S. B. Mitchell, Yuval Nir

Comput. Geom., 2005

On the Fermat-Weber center of a convex object.

Paz Carmi, Sariel Har-Peled, Matthew J. Katz

Comput. Geom., 2005

Geographic Quorum System Approximations.

Paz Carmi, Shlomi Dolev, Sariel Har-Peled, Matthew J. Katz, Michael Segal

Algorithmica, 2005

A constant-factor approximation algorithm for optimal terrain guarding.

Boaz Ben-Moshe, Matthew J. Katz, Joseph S. B. Mitchell

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

The minimum area spanning tree problem.

Paz Carmi, Matthew J. Katz

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

Minimum-Cost Load-Balancing Partitions.

Paz Carmi, Matthew J. Katz

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

2004

Computing all large sums-of-pairs in _Rⁿ and the discrete planar two-watchtower problem.

Boaz Ben-Moshe, Paz Carmi, Matthew J. Katz

Inf. Process. Lett., 2004

Visibility preserving terrain simplification-- an experimental study.

Boaz Ben-Moshe, Matthew J. Katz, Joseph S. B. Mitchell, Yuval Nir

Comput. Geom., 2004

Computing the visibility graph of points within a polygon.

Boaz Ben-Moshe, Olaf A. Hall-Holt, Matthew J. Katz, Joseph S. B. Mitchell

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

2003

Guarding scenes against invasive hypercubes.

Mark de Berg, Haggai David, Matthew J. Katz, Mark H. Overmars, A. Frank van der Stappen, Jules Vleugels

Comput. Geom., 2003

Maintenance of a Piercing Set for Intervals with Applications.

Matthew J. Katz, Frank Nielsen, Michael Segal

Algorithmica, 2003

2002

Walking around fat obstacles.

L. Paul Chew, Haggai David, Matthew J. Katz, Klara Kedem

Inf. Process. Lett., 2002

Improved algorithms for placing undesirable facilities.

Matthew J. Katz, Klara Kedem, Michael Segal

Comput. Oper. Res., 2002

Sixteenth European Workshop on Computational Geometry - Editorial.

Matthew J. Katz, Klara Kedem

Comput. Geom., 2002

Models and motion planning.

Mark de Berg, Matthew J. Katz, Mark H. Overmars, A. Frank van der Stappen, Jules Vleugels

Comput. Geom., 2002

Realistic Input Models for Geometric Algorithms.

Mark de Berg, A. Frank van der Stappen, Jules Vleugels, Matthew J. Katz

Algorithmica, 2002

2001

A Tight Bound on the Number of Geometric Permutations of Convex Fat Objects in <i>R</i>^<i>d</i>.

Matthew J. Katz, Kasturi R. Varadarajan

Discret. Comput. Geom., 2001

Geometry Helps in Bottleneck Matching and Related Problems.

Alon Efrat, Alon Itai, Matthew J. Katz

Algorithmica, 2001

A tight bound on the number of geometric permutations of convex fat objects in R^d.

Matthew J. Katz, Kasturi R. Varadarajan

Proceedings of the Seventeenth Annual Symposium on Computational Geometry, 2001

Farthest neighbors and center points in the presence of rectangular obstacles.

Boaz Ben-Moshe, Matthew J. Katz, Joseph S. B. Mitchell

Proceedings of the Seventeenth Annual Symposium on Computational Geometry, 2001

2000

Computing Euclidean bottleneck matchings in higher dimensions.

Alon Efrat, Matthew J. Katz

Inf. Process. Lett., 2000

Obnoxious Facility Location: Complete Service with Minimal Harm.

Boaz Ben-Moshe, Matthew J. Katz, Michael Segal

Int. J. Comput. Geom. Appl., 2000

Discrete rectilinear 2-center problems.

Matthew J. Katz, Klara Kedem, Michael Segal

Comput. Geom., 2000

Dynamic data structures for fat objects and their applications.

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

Comput. Geom., 2000

Maintenance of a Percing Set for Intervals with Applications.

Matthew J. Katz, Frank Nielsen, Michael Segal

Proceedings of the Algorithms and Computation, 11th International Conference, 2000

Shooter Location through Piercing Sets.

Matthew J. Katz, Frank Nielsen, Michael Segal

EuroCG, 2000

1999

Optimal Line Bipartitions of Point Sets.

Olivier Devillers, Matthew J. Katz

Int. J. Comput. Geom. Appl., 1999

3-Piercing of d-Dimensional Boxes and Homothetic Triangles.

Eyal Assa, Matthew J. Katz

Int. J. Comput. Geom. Appl., 1999

On the union of k-curved objects.

Alon Efrat, Matthew J. Katz

Comput. Geom., 1999

1998

Constrained Square-Center Problems.

Matthew J. Katz, Klara Kedem, Michael Segal

Proceedings of the Algorithm Theory, 1998

On the Union of <i>k</i>-Curved Objects.

Alon Efrat, Matthew J. Katz

Proceedings of the Fourteenth Annual Symposium on Computational Geometry, 1998

1997

An Expander-Based Approach to Geometric Optimization.

Matthew J. Katz, Micha Sharir

SIAM J. Comput., 1997

3-D Vertical Ray Shooting and 2-D Point Enclosure, Range Searching, and Arc Shooting Amidst Convex Fat Objects.

Matthew J. Katz

Comput. Geom., 1997

1996

Computing Fair and Bottleneck Matchings in Geormetric Graphs.

Alon Efrat, Matthew J. Katz

Proceedings of the Algorithms and Computation, 7th International Symposium, 1996

On Piercing Sets of Objects.

Matthew J. Katz, Frank Nielsen

Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

1995

Computing Depth Orders for Fat Objects and Related Problems.

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

Comput. Geom., 1995

Improved Algorithms in Geometric Optimization via Expanders.

Matthew J. Katz

Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

1994

Geometric optimization via expanders and visibility of fat objects in three dimensions: two studies in computational geometry

Matthew J. Katz

PhD thesis, 1994

Computing Depth Orders and Related Problems.

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

Proceedings of the Algorithm Theory, 1994

1993

Verifying plans for multiple agents.

Matthew J. Katz, Jeffrey S. Rosenschein

J. Exp. Theor. Artif. Intell., 1993

Optimal Slope Selection via Expanders.

Matthew J. Katz, Micha Sharir

Inf. Process. Lett., 1993

1992

Efficient Hidden Surface Removal for Objects with Small Union Size.

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

Comput. Geom., 1992

1989

Plans for Multiple Agents.

Matthew J. Katz, Jeffrey S. Rosenschein

Proceedings of the Distributed Artificial Intelligence, 1989