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
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 ans 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)
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, to
appear
Y. Dinitz, M.J. Katz and R. Krakovski
Guarding
rectangular partitions
Int. J. Comput.
Geom. and Appls,
to appear
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, to
appear
E. Horev, M.J.
Katz, R. Krakovski and M. L\”{o}ffler
Polychromatic 4-coloring of guillotine
subdivisions
Information Processing Letters, to
appear
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, to appear
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, to appear
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
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
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
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