Matthew (Matya) Katz, Publications
I. Book
Chapters
M.J. Katz and J.S.
Rosenschein
Plans for Multiple Agents
Distributed Artificial Intelligence Vol. II, L.
Gasser and M.N. Huhns (eds.), Pitman, 1989, pp.
197-228
II. Papers in
Journals (by Publication Date)
M.J. Katz, M.H. Overmars and M. Sharir
Efficient hidden surface removal for objects
with small union size (ps)
Comp. Geom., Theory and Appls
2 (1992), 223-234
M.J. Katz and J.S.
Rosenschein
The generation and execution
of plans for multiple agents
Computers and Artificial Intelligence 12
(1993), 5-35
M.J. Katz and J.S.
Rosenschein
Verifying plans for multiple agents
J. Expt. Theor. Artif. Intell. 5
(1993), 39-56
M.J. Katz and M.
Sharir
Optimal slope selection via expanders (ps)
Information Processing Letters 47 (1993),
115-122
P.K. Agarwal, M.J.
Katz and M. Sharir
Computing depth orders and related problems (ps)
Comp. Geom., Theory and Appls
5 (1995), 187-206
M.J. Katz and M.
Sharir
An expander-based
approach to geometric optimization (ps)
SIAM J. Computing 26 (1997),
1384-1408
M.J. Katz
3-D vertical ray shooting and 2-D point
enclosure, range searching, and arc shooting, amidst convex fat objects (ps)
Comp. Geom., Theory and Appls
8 (1997), 299-316
O. Devillers and M.J. Katz
Optimal line bipartitions of point sets (ps)
Int. J. Comput.
Geom. and Appls 9 (1999), 39-52
E. Assa and M.J. Katz
3-piercing of $d$-dimensional boxes and homothetic
triangles (ps)
Int. J. Comput.
Geom. and Appls 9 (1999), 249-260
A. Efrat and M.J.
Katz
On the union of $\kappa$-curved objects (ps)
Comp. Geom., Theory and Appls
14 (1999), 241-254
A. Efrat and M.J.
Katz
Computing Euclidean bottleneck matchings in higher dimensions (ps)
Information Processing Letters 75(4)
(2000), 169-174
M.J. Katz, K.
Kedem and M. Segal
Discrete rectilinear 2-center problems (ps)
Comp. Geom., Theory and Appls
15 (2000), 203-214
B. Ben-Moshe, M.J.
Katz and M. Segal
Obnoxious facility location: complete service
with minimal harm (ps)
Int. J. Comput. Geom.
and Appls 10 (2000), 581-592
A. Efrat, M.J.
Katz, F. Nielsen, and M. Sharir
Dynamic data structures for fat objects and
their applications (ps)
Comp. Geom., Theory and Appls
15 (2000), 215-227
A. Mizrahi, E.
Ben-ner, M.J. Katz, K. Kedem, G. Glusman
and F. Libersat
Comparative analysis of dendritic
architecture of identified neurons using the Hausdorff
distance metric
J. Comparative Neurology 422 (2000),
415-428
A. Efrat, A. Itai and M.J. Katz
Geometry helps in bottleneck matching and
related problems (ps)
Algorithmica 31 (2001), 1-28
M.J. Katz and K.R.
Varadarajan
A tight bound on the number of geometric
permutations of convex fat objects in $\reals^d$ (ps)
Discrete & Computational Geometry 26
(2001), 543-548
M.J. Katz, K.
Kedem and M. Segal
Improved algorithms for placing undesirable
facilities (ps)
Computers and Operations Research 29 (2002),
1859-1872
M. de Berg, M.J.
Katz, A.F. van der Stappen
and J. Vleugels
Realistic input models for geometric algorithms (ps)
Algorithmica 34 (2002), 81-97
M. de Berg, M.J.
Katz, M. Overmars, A.F. van der
Stappen and J. Vleugels
Models and motion planning (ps)
Comp. Geom., Theory and Appls
23 (2002), 53-68
L.P. Chew, H. David,
M.J. Katz and K. Kedem
Walking around fat obstacles (ps)
Information Processing Letters 83 (2002),
135-140
M. de Berg, H.
David, M.J. Katz, M. Overmars, A.F. van der Stappen and J. Vleugels
Guarding scenes against invasive hypercubes (ps)
Comp. Geom., Theory and Appls
26 (2003), 99-117
M.J. Katz, F.
Nielsen and M. Segal
Maintenance of a piercing set for intervals with
applications (ps)
Algorithmica 36 (2003), 59-73
B. Ben-Moshe, P.
Carmi and M.J. Katz
Computing all large sums-of-pairs in $\reals^n$ and the discrete planar two-watchtower problem (ps)
Information Processing Letters 89 (2004),
137-139
B. Ben-Moshe, M.J.
Katz, J.S.B. Mitchell and Y. Nir
Visibility preserving terrain simplification -
An experimental study (ps)
Comp. Geom., Theory and Appls
28 (2004), 175-190
M.J. Katz, J.S.B.
Mitchell and Y. Nir
Orthogonal segment stabbing (ps)
Comp. Geom., Theory and Appls
30 (2005), 197-205
P. Carmi, S.
Dolev, S. Har-Peled, M.J. Katz and M. Segal
Geographic quorum systems approximations (ps)
Algorithmica 41 (2005), 233-244
P. Carmi, S.
Har-Peled and M.J. Katz
On the Fermat-Weber center of a convex object (ps)
Comp. Geom., Theory and Appls
32 (2005), 188-195
M. de Berg, J.
Gudmundsson, M.J. Katz, C. Levcopoulos, M. Overmars and A.F. van der Stappen
TSP with neighborhoods of varying size (pdf)
J. of Algorithms 57 (2005), 22--36
P. Carmi and M.J.
Katz
Power assignment in radio networks with two
power levels (ps)
Algorithmica 47 (2007), 183-201
P. Carmi, M.J.
Katz and J.S.B. Mitchell
The minimum area spanning tree problem (ps)
Comp. Geom. Theory and Appls
35 (2006), 218-225
B. Ben-Moshe, P.
Carmi and M.J. Katz
Approximating the visible region of a point on a
terrain (ps)
GeoInformatica
12 (2008), 21-36
B. Ben-Moshe,
M.J. Katz and J.S.B. Mitchell
A constant-factor approximation algorithm
for optimal 1.5D terrain guarding (ps)
SIAM J. Computing 36 (2007), 1631-1647
P. Carmi,
M.J. Katz and N. Lev-Tov
Polynomial-time approximation schemes for
piercing and covering with applications in wireless networks
Comp. Geom. Theory and Appls
39 (2008), 209-218
M.J. Katz
and G.S. Roisman
On guarding
rectilinear domains
Comp. Geom. Theory and Appls
39 (2008), 219-228
P. Carmi,
M.J. Katz, M. Segal and H. Shpungin
Fault-tolerant power assignment and
backbone in wireless networks
Ad Hoc & Sensor Wireless Networks 4
(2007), 355-366
B. Aronov,
P. Carmi and M.J. Katz
Minimum-cost load-balancing partitions
Algorithmica 54 (2009), 318-336
Y. Dinitz,
M.J. Katz and R. Krakovski
Guarding rectangular partitions
Int. J. Comput. Geom. and Appls 19 (2009), 579-594
A.K. Abu-Affash
and M.J. Katz
Improved bounds on the average distance to the
Fermat-Weber center of a convex object
Information Processing Letters 109
(2009), 329-333
E. Horev, M.J.
Katz, R. Krakovski and M. L\”{o}ffler
Polychromatic 4-coloring of guillotine
subdivisions
Information Processing Letter 109
(2009), 690-694
M.J. Katz, N. Lev-Tov and G. Morgenstern
Conflict-free coloring of points on a line with
respect to a set of intervals
Comp. Geom. Theory and Appls
45 (2012), 508-514
M.J. Katz and G.
Morgenstern
A scheme for computing minimum covers within
simple regions
Algorithmica 62 (2012), 349-360
M.J.
Katz and G. Morgenstern
Guarding orthogonal art galleries
with sliding cameras
Int. J. Comput.
Geom. and Appls 21 (2011), 241-250
M.J. Katz and G.
Morgenstern
Settling the bound on the
rectilinear link radius of a simple rectilinear polygon
Information Processing
Letter 111 (2011), 103-106
P. Carmi, M.J.
Katz, Z. Lotker and Adi Rosen
Connectivity guarantees for wireless
networks with directional antennas
Comp. Geom. Theory and Appls 44
(2011), 477-485
A.K. Abu-Affash,
R. Aschner, P. Carmi and M.J. Katz
Minimum power energy spanners in
wireless ad hoc networks
Wireless Networks 17 (2011), 1251-1258
A.K.
Abu-Affash, R. Aschner, P. Carmi and M.J. Katz
The
MST of symmetric disk graphs is light
Comp. Geom. Theory and Appls
45 (2012), 54-61
H. Kaplan, M.J. Katz, G. Morgenstern and M.
Sharir
Optimal cover of points by disks in a simple polygon
SIAM J. Computing 40
(2011), 1647-1661
E.
Horev, M.J. Katz, R. Krakovski and A. Nakamoto
Polychromatic 4-coloring of cubic
bipartite plane graphs
Discrete
Mathematics 312 (2012), 715-719
A.K. Abu-Affash, P. Carmi, M.J. Katz and G. Morgenstern
Multi cover of a polygon minimizing the sum of
areas
Int. J. Comput.
Geom. and Appls 21 (2011), 685-698
P. Bose, P.
Carmi, L. Chaitman, S. Collete, M.J. Katz and S.
Langerman
Stable roommates
spanner,
Comp. Geom. Theory and Appls, accepted
P. Bose, P.
Carmi, M. Damian, R. Flatland, M.J. Katz and A. Maheshwari
Switching to directional antennas with
constant increase in radius and hop distance
Algorithmica, accepted
III. Papers in
Proceedings of Refereed Conferences (by Publication Date)
M.J. Katz, M.H. Overmars and M. Sharir
Efficient hidden surface removal for objects
with small union size
Proc. 7th ACM Symp.
on Computational Geometry, 1991, 31-40
M.J. Katz and M.
Sharir
An expander-based approach to geometric
optimization
Proc. 9th ACM Symp.
on Computational Geometry, 1993, 198-207
P.K. Agarwal, M.J.
Katz and M. Sharir
Computing depth orders and related problems
Proc. 4th Scandinavian Workshop on Algorithm
Theory, 1994, 1-12, LNCS 824
M.J. Katz
Improved algorithms in geometric optimization
via expanders
Proc. 3rd Israel Symp.
on Theory of Computing and Systems, 1995, 78-87
M.J. Katz and F.
Nielsen
On piercing sets of objects (ps)
Proc. 12th ACM Symp. on Computational Geometry, 1996, 113-121
O. Devillers and M.J. Katz
Optimal line bipartitions of point sets
Proc. 7th Int. Symp.
on Algorithms and Computation, 1996, 45-54, LNCS 1178
A. Efrat and M.J.
Katz
Computing fair and bottleneck matchings in geometric graphs
Proc. 7th Int. Symp.
on Algorithms and Computation, 1996, 115-125, LNCS 1178
M. de Berg, M.J.
Katz, A.F. van der Stappen
and J. Vleugels
Realistic input models for geometric algorithms
Proc. 13th ACM Symp.
on Computational Geometry, 1997, 294-303
A. Efrat, M.J. Katz,
F. Nielsen, and M. Sharir
Dynamic data structures for fat objects and
their applications
Proc. Workshop on Algorithms and Data
Structures, 1997, 297-306, LNCS 1272
A. Efrat and M.J.
Katz
On the union of $\kappa$-curved objects
Proc. 14th ACM Symp.
on Computational Geometry, 1998, 206-213
M.J. Katz, K.
Kedem and M. Segal
Constrained square-center problems
Proc. 6th Scandinavian Workshop on Algorithm
Theory, 1998, 95-106, LNCS 1432
M. de Berg, M.J.
Katz, M. Overmars, F. van der
Stappen and J. Vleugels
Models and motion planning
Proc. 6th Scandinavian Workshop on Algorithm
Theory, 1998, 83-94, LNCS 1432
M. de Berg, H.
David, M.J. Katz, M. Overmars, A.F. van der Stappen and J. Vleugels
Guarding scenes against invasive hypercubes
Proc. 2nd Workshop on Algorithm Engineering,
1998, 110-120
M.J. Katz, F.
Nielsen and M. Segal
Maintenance of a piercing set for intervals on
the line with applications
Proc. 11th Int. Symp.
on Algorithms and Computation, 2000, 552-563, LNCS
1969
B. Ben-Moshe, M.J.
Katz and J.S.B. Mitchell
Farthest neighbors and center points in the
presence of rectangular obstacles (ps)
Proc. 17th ACM Symp.
on Computational Geometry, 2001, 164-171
M.J. Katz and K.R.
Varadarajan
A tight bound on the number of geometric
permutations of convex fat objects in ${\cal R}^d$
Proc. 17th ACM Symp.
on Computational Geometry, 2001, 249-251
B. Ben-Moshe, M.J.
Katz, J.S.B. Mitchell and Y. Nir
Visibility preserving terrain simplification -
An experimental study
Proc. 18th ACM Symp.
on Computational Geometry, 2002, 303-311
M. de Berg, J.
Gudmundsson, M.J. Katz, C. Levcopoulos, M. Overmars and A.F. van der Stappen
TSP with neighborhoods of varying size
Proc. 10th European Symp.
on Algorithms, 2002, 187-199
B. Ben-Moshe, P.
Carmi and M.J. Katz
Approximating the visible region of a point on a
terrain
Proc. Algorithm Engineering &
Experiments, 2004, 120-128
B. Ben-Moshe, O.
Hall-Holt, M.J. Katz and J.S.B. Mitchell
Computing the visibility graph of points within
a polygon (ps)
Proc. 20th ACM Symp.
on Computational Geometry, 2004, 27-35
P. Carmi and M.J.
Katz
Power assignment in radio networks with two
power levels
Proc. 9th Scandinavian Workshop on Algorithm
Theory, 2004, 431-441
B. Ben-Moshe, M.J.
Katz and J.S.B. Mitchell
A constant-factor approximation algorithm for optimal
terrain guarding (ps)
Proc. 16th ACM-SIAM Symp.
Discrete Algorithms, 2005, 515-524
P. Carmi, M.J.
Katz and J.S.B. Mitchell
The minimum area spanning tree problem
Proc. Workshop on Algorithms and Data
Structures, 2005, 195-204, LNCS 3608
O. Hall-Holt, M.J.
Katz, P. Kumar, J. S. B. Mitchell and A. Sityon
Finding large sticks and potatoes in polygons (pdf)
Proc. 17th ACM-SIAM Symp.
Discrete Algorithms, 2006, 474-483
P. Carmi, M.J.
Katz, M. Segal and H. Shpungin
Fault-tolerant power assignment and backbone in
wireless networks (ps)
Proc. IEEE Internat.
Workshop on Foundations and Algorithms for Wireless Networking, 2006
B. Aronov, P.
Carmi and M.J. Katz
Minimum-cost load-balancing partitions (ps)
Proc. 22nd ACM Symp.
on Computational Geometry, 2006, 301-308
M.J. Katz and G.S.
Roisman
On guarding rectilinear
domains
Proc. 10th Scandinavian Workshop on Algorithm
Theory, 2006, 220-231
P. Carmi, M.J.
Katz and N. Lev-Tov
Covering points by unit disks of fixed location
Proc. 18th Internat.
Symp.
on Algorithms and Computation, 2007, 644-655
M.J. Katz and G.
Morgenstern
A scheme for computing minimum covers within
simple regions
Proc. 20th Algorithms and Data Structures Symp., 2009, 447-458
A.K. Abu-Affash,
R. Aschner, P. Carmi and M.J. Katz
Minimum power energy spanners in wireless ad hoc
networks
Proc. 29th IEEE Conference on Computer
Communications, 2010, 2411-2416
A.K. Abu-Affash,
R. Aschner, P. Carmi and M.J. Katz
The MST of symmetric
disk graphs is light
Proc. 12th Scandinavian Workshop on Algorithm
Theory, 2010, 236-247
H. Kaplan, M.J.
Katz, G. Morgenstern and M. Sharir
Optimal cover of points by disks in a simple
polygon
Proc. 18th European Symp.
on Algorithms, 2010, 475-486
A.K. Abu-Affash,
P. Carmi, M.J. Katz and G. Morgenstern
Multi cover of a polygon minimizing the sum of
areas
Proc. 5th Internat.
Workshop on Algorithms and Computation, 2011, 134-145
A.K.
Abu-Affash, P. Carmi, M.J. Katz and M. Segal
The
Euclidean Bottleneck Steiner Path Problem
Proc. 27th ACM Symp. on Computational Geometry,
2011, 440-447
P. Bose, P. Carmi,
M. Damian, R. Flatland, M.J. Katz and A. Maheshwari
Switching to directional antennas
with constant increase in radius and hop distance
Proc. 12th Algorithms
and Data Structures Symp., 2011, 134-146
R. Aschner, M.J. Katz and G. Morgenstern
Do directional antennas facilitate
in reducing interferences?
Proc. 13th Scandinavian Symp.
and Workshops on Algorithm Theory, 2012, 201-212
A.K. Abu-Affash, P. Carmi, M.J. Katz and Y.
Trabelsi
Bottleneck non-crossing matching in
the plane
Proc. 20th European Symp. on Algorithms, 2012,
36-47
R. Aschner, M.J. Katz and G. Morgenstern
Symmetric connectivity with directional antennas
Proc.8th Internat. Symp. on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS'12), 2012, accepted
R. Aschner, M.J. Katz, G. Morgenstern and Y.
Yuditsky
Approximation schemes for covering and packing
Proc. 7th Internat. Workshop on Algorithms and Computation, 2013, accepted
IV. Other
M.J. Katz and J.S.
Rosenschein
Plans for multiple agents
Proc. AAAI Workshop on Distributed Artificial
Intelligence, 1988
M.J. Katz and M.
Sharir
Optimal slope selection via expanders
Proc. 5th Canadian Conf. on Computational
Geometry, 1993, 139-144
B. Ben-Moshe, M.J.
Katz and M. Segal
Obnoxious facility location: complete service
with minimal harm
Proc. 11th Canadian Conf. on Computational
Geometry, 1999, 76--79
M.J. Katz, K.
Kedem and M. Segal
Improved algorithms for placing undesirable
facilities
Proc. 15th European Workshop on Computational
Geometry, 1999, 39-42
Proc. 11th Canadian Conf. on Computational
Geometry, 1999, 65-67
A. Mizrahi, E.
Ben-ner, J.G. Glusman, M.J.
Katz, K. Kedem and F. Libersat
Comparative analysis of dendritic
architecture of identified neurons using the hausdorff
distance metric
Abstracts of the 8th annual meeting of the
Israel Society for Neurosciences;
Neuroscience Letters Supplement, 1999, 54, S30
M.J. Katz, F.
Nielsen and M. Segal
Shooter location through piercing sets
Proc. 16th European Workshop on Computational
Geometry, 2000, 55-58
S. Bespamyatnikh, M.J. Katz, F. Nielsen and M. Segal
Visibility queries among horizontal segments - a
dynamic data structure
Proc. Japan Conference on Discrete and
Computational Geometry, 2000
B. Ben-Moshe and
M.J. Katz
Approximating the diameter of a set of points in
the Presence of rectangular obstacles
Proc. 17th European Workshop on Computational
Geometry, 2001, 154-157
P. Carmi and M.J.
Katz
Minimizing the convex hull via local transfers
Proc. 17th European Workshop on Computational
Geometry, 2001, 105-108
M.J. Katz, J.S.B.
Mitchell and Y. Nir
Orthogonal segment stabbing
Proc. 19th European Workshop on Computational
Geometry, 2003, 129-132
B. Ben-Moshe, P.
Carmi and M.J. Katz
Approximating the visible region of a point on a
terrain
Proc. 19th European Workshop on Computational
Geometry, 2003, 121-124
P. Carmi and M.J.
Katz
The minimum area
spanning tree problem
Proc. 21st European Workshop on Computational
Geometry, 2005, 191-194
P. Carmi and M.J.
Katz
Minimum-cost load-balancing partitions
Proc. 17th Canadian Conf. on Computational
Geometry, 2005, 63-65
Y. Dinitz, M.J.
Katz and R. Krakovski
Guarding rectangular partitions
Proc. 23rd European Workshop on Computational
Geometry, 2007, 30-33
M.J. Katz, N. Lev-Tov and G. Morgenstern
Conflict-free coloring of points on a line with
respect to a set of intervals
Proc. 19th Canadian Conf. on Computational
Geometry, 2007, 93-96
B. Ben-Moshe, M.J.
Katz and I. Zaslavsky
Distance preserving terrain simplification - An
experimental study
Proc. 19th Canadian Conf. on Computational
Geometry, 2007, 129-132
A.K. Abu-Affash
and M.J. Katz
Improved bounds on the average distance to the
Fermat-Weber center of a convex object
Proc. 20th Canadian Conf. on Computational
Geometry, 2008, 147-150
Gila Morgenstern
and M.J. Katz
Guarding orthogonal art galleries with sliding
cameras
Proc. 25th European Workshop on Computational
Geometry, 2009, 159-162
B. Ben-Moshe, P.
Carmi, L. Chaitman, M.J. Katz, G. Morgenstern and Y. Stein
Direction assignment in wireless networks
Proc. 22nd Canadian Conf. on Computational
Geometry, 2010, 39-42
A.K. Abu-Affash,
P. Carmi and M.J. Katz
Bottleneck Steiner tree with bounded number
of Steiner vertices
Proc. 23rd Canadian Conf. on Computational
Geometry, 2011, to appear
M.J. Katz
A simple randomized algorithm for the minimum
output rate problem
manuscript
E. Ben-ner, M.J. Katz and K. Kedem
Methods for quantitative analysis of the spatial
structure of dendrites (ps)
manuscript