Adrian Dumitrescu


Associate Professor
Department of Computer Science
University of Wisconsin-Milwaukee
3200 N. Cramer Street
Milwaukee, WI 53211
USA



Phone: 414-229-4265

dumitres[at)u w m(dot]e d u








DIGITAL DRAWINGS AND COMPOSITIONS



PICTURES FROM AN EXHIBITION



Recent Public Appearences, Inside/Outside Jobs, etc.


Mathematical Art Works:

Recursive construction for sliding disks, SIGMAA-ARTS Exhibition of Mathematical Art, held as part of the AMS-MAA Joint Mathematics Meetings, Washington, DC, January 5-8, 2009.
Arrangement (2), Exhibition of Mathematical Art, held as part of the AMS-MAA Joint Mathematics Meetings, San Francisco, California, January 13-16, 2010.


Recent Awards:

DIMACS award for research support, 1999
DIMACS fellowship, 1999
NSF CAREER award, May 2005
Graduate School/UWM Foundation research award, 2006
NSF award, September 2010
Excellence in research award, College of Engineering and Applied Science, UWM, March 2013


Member on the Editorial Board of:

Algorithms

Journal of Universal Computer Science


Research Interests:

Theory of Algorithms,
Computational and Combinatorial Geometry,
Combinatorics,
Combinatorial Number Theory,
Computational Morphology,
Robotics.


Research Support:

My research is currently supported by the National Science Foundation under the grant DMS 1001667.
Previous support (2005 - 2011) was provided under CAREER grant CCF-0444188.


Other:

My Erdös number is 2.


Dates:

1999: PhD in Computer Science from Rutgers University. Advisor: Professor William Steiger.
2000: Postdoctoral position in the Department of Applied Mathematics and Statistics at Stony Brook University. Advisor: Professor Joseph Mitchell.
Jan. 2001 - 2007: Assistant Professor of Computer Science, CS Dept., University of Wisconsin-Milwaukee.
Since Aug. 2007: Associate Professor of Computer Science, CS Dept., University of Wisconsin-Milwaukee.


Past events:

I have organized Midwest Theory Day on Saturday, December 10, 2005.


Courses:

Introduction to the Theory of Computation (CS 417): Fall 2001, Spring 2002, Fall 2002, Spring 2004, Spring 2005, Fall 2006, Fall 2007, Spring 2008, Spring 2011, Spring 2014.
Data Structures and Algorithms (CS 535): Spring 2003, Fall 2003, Spring 2004, Spring 2005, Fall 2005.
Algorithm Design and Analysis (CS 535): Fall 2010, Fall 2011.
Analysis of Algorithms (CS 704): Spring 2001, Spring 2002, Fall 2002, Spring 2003, Fall 2004, Spring 2006, Fall 2007, Fall 2009, Spring 2012, Spring 2013.
Computational Geometry (CS 714): Fall 2003, Fall 2004, Fall 2006, Spring 2010.
Randomized Algorithms and Pseudorandom Numbers(CS 805): Fall 2005, Spring 2007, Fall 2010.


Miscellaneous:


Aoccdrnig to a rscheearch at Cmabrigde Uinervtisy, it deosn't mttaer
in waht oredr the ltteers in a wrod are, the olny iprmoetnt tihng is
taht the frist and lsat ltteer be at the rghit pclae.  The rset can be
a total mses and you can sitll raed it wouthit porbelm.  Tihs is
bcuseae the huamn mnid deos not raed ervey lteter by istlef, but the
wrod as a wlohe.



Papers:

Here is another list of my publications compiled by DBLP, and another one compiled by MathSciNet.

[1] T. Ciortea, A. Dumitrescu, I. Pall, A. Rotaru and S. Rusu, A memory resident software kernel of a testing equipment for SSI-MSI boards, The Second Symposium on Automated Testing, (TETA '83), Cluj, 1983 and in AMC, vol. 46, Editura Tehnica, Bucharest, 1984, 51-57.

[2] T. Ciortea, A. Dumitrescu, A. Rotaru, S. Rusu and B. Stoenescu, An automated testing equipment for digital boards, The Fifth International Conference on automated Systems, (SAII-5), Bucharest, 1983, vol. 3.

[3] S. Ciobanu, A. Dumitrescu, I. Pall and A. Rotaru, Diagnosis functions implementations for a testing equipment, The third Symposium on Automated Testing, (TETA '84), Cluj, 1984.

[4] A. Dumitrescu and A. Rotaru, A guided probe procedure for fault isolation on digital boards, The Sixth International Conference on Automated Systems, (SAII-6), Bucharest, 1985, vol. 2.

[5] A. Dumitrescu, On two lower bound constructions, Eleventh Canadian Conference on Computational Geometry, 1999 (CCCG '99), 111-114.

[6] A. Dumitrescu, Planar sets with few empty convex polygons, Studia Scientiarum Mathematicarum Hungarica, 36(1-2), 2000, 93-109; an extended abstract in Proceedings of the Tenth Canadian Conference on Computational Geometry, 1998 (CCCG '98), 14-15.

[7] A. Dumitrescu and W. Steiger, On a matching problem in the plane, Sixth International Workshop on Algorithms and Data Structures, 1999 (WADS '99), and in Discrete Mathematics, 211(1-3), 2000, 183-195.

[8] A. Dumitrescu and R. Kaye, Matching colored points in the plane: some new results, Computational Geometry: Theory and Applications, 19(1), 2001, 69-85.

[9] A. Dumitrescu, B. Gärtner, S. Pedroni and E. Welzl, Enumerating triangulation paths, Computational Geometry: Theory and Applications, 20(1-2), 2001, 3-12. Special issue of selected papers from CCCG '00. An extended abstract in Proceedings of the Twelfth Canadian Conference on Computational Geometry, 2000 (CCCG '00), 233-238.

[10] A. Dumitrescu and W. Steiger, Space-time trade-offs for some ranking and searching queries, Information Processing Letters, 79(5), 2001, 237-241.

[11] A. Dumitrescu and G. Tóth, Ramsey-type results for unions of comparability graphs, Graphs and Combinatorics, 18(2), 2002, 245-251. A preliminary version in Proceedings of the Eleventh Canadian Conference on Computational Geometry, 1999 (CCCG '99), 178-181.

[12] A. Dumitrescu and J. Pach, Partitioning colored point sets into monochromatic parts, International Journal of Computational Geometry & Applications, 12(5), 2002, 401-412. A preliminary version in Proceedings of the Seventh International Workshop on Algorithms and Data Structures (WADS '01), Lecture Notes in Computer Science, Vol. 2125, 2001, 264-275.

[13] A. Dumitrescu, On the maximum multiplicity of some extreme geometric configurations in the plane, Geombinatorics, 12(1), 2002, 5-14; (with a small correction to the journal version).

[14] A. Dumitrescu and J. Mitchell, Approximation algorithms for TSP with neighborhoods in the plane, Journal of Algorithms, 48(1), 2003, 135-159. Special issue with selected papers from SODA'01. An extended abstract in Proceedings of the Twelfth ACM-SIAM Symposium on Discrete Algorithms, January 2001 (SODA '01), 38-47.

[15] A. Dumitrescu, Efficient algorithms for generation of combinatorial covering suites, Proceedings of the the 14-th Annual International Symposium on Algorithms and Computation (ISAAC '03), Lecture Notes in Computer Science, Vol. 2906, 2003, 300-308.

[16] C. Cheng, A. Dumitrescu and P. Schroeder, Generating small combinatorial test suites to cover input-output relationships, Proceedings of the Third International Conference on Quality Software (QSIC '03), Dallas, November 2003, 76-82.

[17] A. Dumitrescu, J. Mitchell and M. Sharir, Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles, Discrete & Computational Geometry, 31(2), 2004, 207-227. A preliminary version in Proceedings of the Seventeenth Annual Symposium on Computational Geometry, June 2001 (SOCG'01), 141-150.

[18] A. Dumitrescu and S. Guha, Extreme distances in multicolored point sets , Journal of Graph Algorithms and Applications, 8(1), 2004, 27-38. A preliminary version in Proceedings of the Second International Workshop on Computational Geometry and Applications (CGA '02), Amsterdam, April 2002. Lecture Notes in Computer Science, Vol. 2331, 2002, 14-25.

[19] A. Dumitrescu, I. Suzuki and M. Yamashita, Formations for fast locomotion of metamorphic robotic systems, International Journal of Robotics Research, 23(6), 2004, 583-593. A preliminary version in Proceedings of the 2002 IEEE International Conference on Robotics and Automation, (ICRA '02), Washington, May 2002, 123-128.

[20] A. Dumitrescu, I. Suzuki and M. Yamashita, Motion planning for metamorphic systems: feasibility, decidability and distributed reconfiguration, IEEE Transactions on Robotics and Automation, 20(3), 2004, 409-418.

[21] A. Dumitrescu, The cost of cutting out convex n-gons, Discrete Applied Mathematics, 143(1-3), 2004, 353-358.

[22] A. Dumitrescu, An approximation algorithm for cutting out convex polygons, Computational Geometry: Theory and Applications, 29(3), 2004, 223-231. A preliminary version in Proceedings of the Fourteenth ACM-SIAM Symposium on Discrete Algorithms (SODA '03), January 2003, 823-827.

[23] A. Dumitrescu and R. Radoicic, On a coloring problem for the integer grid, in Towards a Theory of Geometric Graphs, János Pach (editor), Contemporary Mathematics series of AMS, 2004, pages 67-74.

[24] A. Dumitrescu and G. Rote, On the Fréchet distance of a set of curves, Proceedings of the Sixteenth Canadian Conference on Computational Geometry, (CCCG '04), August 2004, 162-165.

[25] G. Calinescu and A. Dumitrescu, The carpenter's ruler folding problem, in Combinatorial and Computational Geometry, Jacob Goodman, János Pach and Emo Welzl (editors), Mathematical Sciences Research Institute Publications, Cambridge University Press, 2005, pages 155-166.

[26] G. Araujo, A. Dumitrescu, F. Hurtado, M. Noy and J. Urrutia, On the chromatic number of some geometric type Kneser graphs, Computational Geometry: Theory and Applications, 32, 2005, 59-69. A preliminary version in Proceedings of the 10th Spanish Workshop on Computational Geometry, Sevilla, June 2003, 44-50.

[27] A. Dumitrescu, Monotone paths in line arrangements with a small number of directions, Discrete & Computational Geometry, 33, 2005, 687-697.

[28] A. Dumitrescu, On some monotone path problems in line arrangements, Computational Geometry: Theory and Applications, 32, 2005, 13-25. A preliminary version in Proceedings of the Sixteenth Canadian Conference on Computational Geometry, (CCCG '04), August 2004, 200-203.

[29] A. Dumitrescu, A remark on the Erdös-Szekeres theorem, American Mathematical Monthly, 112(12), 2005, 921-924. A preliminary version in Proceedings of the Sixteenth Canadian Conference on Computational Geometry, (CCCG '04), August 2004, 2-3.

[30] A. Dumitrescu and J. Pach, Pushing squares around, Graphs and Combinatorics, 22(1), (2006), 37-50. A preliminary version in Proceedings of the 20-th Annual Symposium on Computational Geometry, (SOCG'04), NY, June 2004, 116-123.

[31] A. Dumitrescu, On distinct distances from a vertex of a convex polygon, Discrete & Computational Geometry, 36, 2006, 503-509. Special issue with selected papers from SOCG '04. An extended abstract in Proceedings of the 20-th Annual Symposium on Computational Geometry, (SOCG'04), NY, June 2004, 57-59.

[32] G. Calinescu, A. Dumitrescu, H. Karloff and Peng-Jun Wan, Separating points by axis-parallel lines, International Journal of Computational Geometry & Applications, 15(6), 2005, 575-590. Special issue with selected papers from CCCG '04.

[33] A. Dumitrescu, A. Ebbers-Baumann, A. Grüne, R. Klein and G. Rote, On the geometric dilation of closed curves, graphs, and point sets, Computational Geometry: Theory and Applications, 36(1), 2006, 16-38. Special issue with selected papers from 21st European Workshop on Computational Geometry, (EWCG '05) Eindhoven, March 2005. Journal version also includes results from: On geometric dilation and halving chords, Proceedings of the Nineth International Workshop on Algorithms and Data Structures, (WADS '05), Waterloo, August 2005. Lecture Notes in Computer Science, Vol. 3608, 2005, 244-255.

[34] S. Bereg, A. Dumitrescu and J. Pach, Sliding disks in the plane, International Journal of Computational Geometry & Applications, 18(5), 2008, 373-387. A preliminary version in Proceedings of Japan Conference on Discrete and Computational Geometry, (JCDCG '04), October 2004, vol. 3742 of LNCS, pp. 37-47.

[35] S. Bereg and A. Dumitrescu, The lifting model for reconfiguration, Discrete & Computational Geometry, 35(4), 2006, 653-669. A preliminary version in Proceedings of the 21st Annual Symposium on Computational Geometry, (SOCG '05), Pisa, Italy, June 2005, 55-62.

[36] A. Dumitrescu, J. Pach and G. Tóth, The maximum number of empty congruent triangles determined by a point set, Revue Roumaine de Mathematiques Pures et Appliquees, 50, 2005, 613-618.

[37] G. Calinescu, A. Dumitrescu and J. Pach, Reconfigurations in graphs and grids, SIAM Journal on Discrete Mathematics, 22(1), 2008, 124-138. A preliminary version in Proceedings of Latin American Theoretical Informatics Symposium, (LATIN '06), Valdivia, Chile, March 2006, Lecture Notes in Computer Science, Vol. 3887, 2006, 262-273.

[38] A. Dumitrescu and Cs. D. Tóth, On the number of tetrahedra with minimum, unit, and distinct volumes in three-space, Combinatorics, Probability and Computing, 17(2), 2008, 203-224. A preliminary version in Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, (SODA '07), New Orleans, January 2007, ACM Press, 1114-1123.

[39] A. Dumitrescu and Cs. D. Tóth, Light orthogonal networks with constant geometric dilation. A preliminary version in Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science, (STACS '07), Aachen, Germany, February 2007. Vol. 4393 of Lecture Notes in Computer Science, Springer Verlag, 2007, 175-187.

[40] S. Bereg, P. Bose, A. Dumitrescu, F. Hurtado and P. Valtr, Traversing a set of points with a minimum number of turns, Discrete & Computational Geometry, 41(4), 2009, 513-532. A preliminary version in Proceedings of the 23rd Annual Symposium on Computational Geometry, (SOCG '07), Gyeongju, South-Korea, June 2007, 46-55.

[41] A. Dumitrescu and Cs. D. Tóth, Distinct triangle areas in a planar point set, Proceedings of the 12th Conference on Integer Programming and Combinatorial Optimization, (IPCO '07), Cornell University, Ithaca, NY, June 2007; vol. 4513 of LNCS, Springer, pp. 119-129.

[42] A. Dumitrescu, Motion planning and reconfiguration for systems of multiple objects; in Mobile Robots: Perception & Navigation, Sascha Kolski (editor), Advanced Robotic Systems, 2007, pages 523-542. [Note: The printed version has many misprints and errors which have been introduced by the publisher. You are advised to use this online version instead.]

[43] A. Dumitrescu, M. Sharir and Cs. D. Tóth, Extremal problems on triangle areas in two and three dimensions, Journal of Combinatorial theory, Ser. A, 116(7), 2009, 1177-1198. An extended abstract in Proceedings of the 24th Annual Symposium on Computational Geometry, (SOCG '08), College Park, Maryland, USA, June 2008, 208-217. Preliminary results in Abstracts of the 16th Fall Workshop on Computational Geometry, November 2006.

[44] A. Dumitrescu, I. Suzuki, and P. Zylinski, Offline variants of the “lion and man” problem, Theoretical Computer Science, 399(3), 2008, 220-235. A preliminary version in Proceedings of the 23rd Annual Symposium on Computational Geometry, (SOCG '07), Gyeongju, South-Korea, June 2007, 102-111.

[45] A. Dumitrescu and G. Xu, On two representation problems with infinite multiplicity, JP Journal of Algebra, Number Theory and Applications, 9(2), 2007, 215-236.

[46] A. Dumitrescu, On distinct distances and λ-free point sets, Discrete Mathematics, 308 (2008), 6533-6538.

[47] A. Dumitrescu and Cs. D. Tóth, Analysis of two sweep-line algorithms for constructing spanning trees and Steiner trees, Journal of Universal Computer Science, 13(11), 2007, 1615-1627. A preliminary version in Abstracts of 17th Fall Workshop on Computational and Combinatorial Geometry, (FWCG '07).

[48] A. Dumitrescu and Cs. D. Tóth, Minimum weight convex Steiner partitions, Algorithmica, 60(3), 2011, 627-652. A preliminary version in Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA '08), San Francisco, January 2008, ACM Press, 581-590.

[49] A. Dumitrescu and Cs. D. Tóth, On stars and Steiner stars, Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA '08), San Francisco, January 2008, ACM Press, 1233-1240.

[50] A. Dumitrescu and G. Xu, On a query algorithm for a divisibility problem, Communications in Computer Algebra, 41(4), 2007, 122-125.

[51] O. Aichholzer, S. Bereg, A. Dumitrescu, A. García, C. Huemer, F. Hurtado, M. Kano, A. Márquez, D. Rappaport, S. Smorodinsky, D. Souvaine, J. Urrutia, and D. Wood, Compatible geometric matchings, Computational Geometry: Theory and Applications, 42(6-7), 2009, 617-626. Preliminary versions in Abstracts of the 17th Fall Workshop on Computational and Combinatorial Geometry (FWCG 2007), November 2007, and Proceedings of Topological & Geometric Graph Theory International Conference (TGGT 2008), Paris, May 2008, Electronic Notes in Discrete Mathematics, 31, 2007, 201-206.

[52] S. Bereg, A. Dumitrescu and M. Jiang, Maximum area independent sets in disk intersection graphs, International Journal of Computational Geometry & Applications, 20(2), 2010, 105-118.

[53] A. Dumitrescu and M. Jiang, On a covering problem for equilateral triangles, The Electronic Journal of Combinatorics, 15(1), #R37, 2008.

[54] A. Dumitrescu, H. Kok, I. Suzuki, and P. Zylinski, Vision-based pursuit-evasion in a grid, SIAM Journal on Discrete Mathematics, 24(3), 2010, 1177-1204. A preliminary version in Proceedings of the 11th Scandinavian Workshop on Algorithm Theory, (SWAT 2008), Gothenburg, Sweden, July 2008; vol. 5124 of LNCS, Springer, pp. 53-64.

[55] S. Bereg, A. Dumitrescu and M. Jiang, On covering problems of Rado, Algorithmica, 57, 2010, 538-561. Special issue with selected papers from SWAT 2008. A preliminary version in Proceedings of the 11th Scandinavian Workshop on Algorithm Theory, (SWAT 2008), Gothenburg, Sweden, July 2008; vol. 5124 of LNCS, Springer, pp. 294-305.

[56] A. Dumitrescu, On distinct distances among points in general position and other related problems, Periodica Mathematica Hungarica, 57(2), 2008, 165-176. A preliminary version in Proceedings of the 20th Canadian Conference on Computational Geometry, (CCCG 2008), 67-70.

[57] A. Dumitrescu and M. Jiang, Monochromatic simplices of any volume, Discrete Mathematics, 310, 2010, 956-960. A preliminary version in Proceedings of the 20th Canadian Conference on Computational Geometry, (CCCG 2008), 71-74.

[58] A. Dumitrescu and M. Jiang, Sweeping points, Algorithmica, 60(3), 2011, 703-717. An earlier version in Proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems , (APPROX 2008), MIT, Boston, USA, August 2008; Vol. 5171 of LNCS, Springer, pp. 63-76.

[59] A. Dumitrescu, Cs. D. Tóth and G. Xu, On stars and Steiner stars, Discrete Optimization, 6(3), 2009, 324-332. contains the results from both SODA'08 and SODA'09 versions. An earlier version On stars and Steiner stars. II, in Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), New York, January 2009, ACM Press.

[60] A. Dumitrescu, M. Jiang, and Cs. D. Tóth, New bounds on the average distance from the Fermat-Weber center of a planar convex body, Discrete Optimization, 8(3), 2011, 417-427. A preliminary version (now obsolete) in: Proceedings of the 20th International Symposium on Algorithms and Computation, (ISAAC 2009), Hawaii,USA, December 2009. An earlier short version in: Abstracts of the 18th Fall Workshop on Computational and Combinatorial Geometry (FWCG 2008), November 2008.

[61] A. Dumitrescu and M. Jiang, Covering a disk by disks, Beiträge zur Algebra und Geometrie, 51(1), 2010, 91-109.

[62] A. Dumitrescu and M. Jiang, On reconfiguration of disks in the plane and other related problems, Computational Geometry: Theory and Applications, 46(3), 2013, 191-202. An extended abstract in: Proceedings of the 23rd International Workshop on Algorithms and Data Structures, (WADS 2009), Banff, August 2009, vol. 5664 of LNCS, Springer, pp. 254-265.

[63] A. Dumitrescu and M. Jiang, Piercing translates and homothets of a convex body, Special issue of Algorithmica with selected papers from ESA 2009. A short version in: Proceedings of the 17th Annual European Symposium on Algorithms, (ESA 2009), Copenhagen, Sept. 2009, vol. 5757 of LNCS, Springer, pp. 131-142.

[64] A. Dumitrescu and Cs. D. Tóth, Long non-crossing configurations in the plane, Discrete & Computational Geometry, 44(4), 2010, 727-752. A preliminary version in Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, (STACS 2010), Nancy, France, March 2010, pp. 299-310.

[65] A. Dumitrescu and M. Jiang, The forest hiding problem, Discrete & Computational Geometry, 45, 2011, 529-552. A preliminary version in Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms, (SODA 2010), Austin, Texas, Jan. 2010, pp. 1566-1579.

[66] A. Dumitrescu, Approximate Euclidean Ramsey theorems, Journal of Computational Geometry, 2(1), 2011, 16-29. A preliminary version in Proceedings of the 22nd Canadian Conference on Computational Geometry, (CCCG 2010), Winnipeg, Manitoba, Canada, August 2010, pp. 131-134.

[67] A. Dumitrescu, J. Pach and G. Tóth, Drawing Hamiltonian cycles with no large angles, Proceedings of the 17th International Symposium on Graph Drawing, (GD 2009), Chicago, Volume 5849 of LNCS, Springer Verlag, March 2010, pp. 3-14.

[68] A. Dumitrescu and J. Pach, Minimum clique partition in unit disk graphs, JCCGG 2009 special issue of Graphs and Combinatorics, 27(3), 2011, 399-411.

[69] A. Dumitrescu and M. Jiang, On the largest empty axis-parallel box amidst n points, Algorithmica, 66(2), 2013, 225-248. Online first, March 2012; DOI 10.1007/s00453-012-9635-5. Also available on arxiv.

[70] A. Dumitrescu and M. Jiang, Dispersion in disks, Theory of Computing Systems, 51(2), 2012, 125-142; special issue with selected papers from STACS 2010. An extended abstract in Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, (STACS 2010), Nancy, France, March 2010, pp. 311-322.

[71] A. Dumitrescu, J. Pach and G. Tóth, A note on blocking visibility between points, Geombinatorics, 19(1), 2009, 67-73.

[72] A. Dumitrescu and M. Jiang, Minimum-perimeter intersecting polygons, Algorithmica, 63(3), 2012, 602--615. Special issue with invited papers from the LATIN 2010 conference. A preliminary version in Proceedings of the 9th Latin American Theoretical Informatics Symposium, (LATIN 2010), Oaxaca, Mexico, April 2010, LNCS Vol. 6034, 433-445.

[73] A. Dumitrescu, Going around in circles, Computational Geometry: Theory and Applications, 45 (2012), 370-381.

[74] A. Dumitrescu and E. Hilscher, On convexification of polygons by pops, Discrete Mathematics, 310, 2010, 2542-2545. A short abstract (Video/Multimedia Session) in Proceedings of the 26th Annual Symposium on Computational Geometry, (SOCG 2010), Snowbird, Utah, June 2010.

[75] A. Dumitrescu and J. Fowler, On simultaneous geometric embedding without mapping and no common edges, manuscript, 2009.

[76] A. Dumitrescu and M. Jiang, Coloring translates and homothets of a convex body, Beiträge zur Algebra und Geometrie, 53(2), 2012, 365-377. Also available on arxiv.

[77] A. Dumitrescu, The traveling salesman problem for lines and rays in the plane, Discrete Mathematics, Algorithms and Applications, 4(4), 2012, 1250044 (12 pages); also available on arxiv. An earlier version in Proceedings of the 22nd Canadian Conference on Computational Geometry, (CCCG 2010), Winnipeg, Manitoba, Canada, August 2010, pp. 257-260.

[78] A. Dumitrescu and Cs. D. Tóth, Watchman tours for polygons with holes, Computational Geometry: Theory and Applications, 45 (2012), 326-333. A preliminary version in Proceedings of the 22nd Canadian Conference on Computational Geometry, (CCCG 2010), Winnipeg, Manitoba, Canada, August 2010, pp. 113-116.

[79] A. Dumitrescu and M. Jiang, Constrained k-center and movement to independence, Discrete Applied Mathematics, 159(8), 2011, 859-865. A preliminary version in Proceedings of the 22nd Canadian Conference on Computational Geometry, (CCCG 2010), Winnipeg, Manitoba, Canada, August 2010, pp. 233-236.

[80] A. Dumitrescu, M. Jiang and J. Pach, Opaque sets, Algorithmica, 69, 2014, 315-334. Online first, December 2012; DOI 10.1007/s00453-012-9735-2. A preliminary version in Proceedings of the 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, (APPROX 2011), Princeton, New Jersey, August 2011, LNCS Vol. 6845, 194-205. Also available on arxiv. [Note: proof of Lemma 1 has a gap; a corrected proof appears in this arxiv version. In fact, this lemma is of a general interest and not needed in the paper.]

[81] A. Dumitrescu, A. Schulz, A. Sheffer, and Cs. D. Tóth, Bounds on the maximum multiplicity of some common geometric graphs, SIAM Journal on Discrete Mathematics, 27(2), 2013, 802-826. An earlier version in Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), Dortmund, Germany, March 2011. Also available on arxiv.

[82] A. Dumitrescu and E. Hilscher, Animal testing, Proceedings of the the 22nd International Symposium on Algorithms and Computation, (ISAAC 2011), Yokohama, Japan, Vol. 7074 of LNCS, Springer, pp. 220-229. A short version in Abstracts of the 20th Fall Workshop on Computational Geometry (FWCG 2010), October 29-30, 2010.

[83] A. Dumitrescu and M. Jiang, Sweeping an oval to a vanishing point, Discrete Applied Mathematics, 159(14), 2011, 1436-1442. A short version in Proceedings of the XIV Spanish Meeting on Computational Geometry, (EGC 2011), June 2011, pp. 59-62. Also available on arxiv.

[84] A. Dumitrescu, Mover problems, in Thirty Essays in Geometric Graph Theory, János Pach (editor), Springer, New York, 2012.

[85] A. Dumitrescu, J. Mitchell and P. Zylinski, Watchman routes for lines and segments, Computational Geometry: Theory and Applications, submitted. A preliminary version in Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012), Helsinki, Finland, July 2012, Vol. 7357 of LNCS, Springer, pp. 36-47.

[86] A. Dumitrescu and M. Hasan, Cutting out polygons with a circular saw, International Journal of Computational Geometry & Applications, 23(2), 2013, 127-139. Special issue with invited papers from the ISAAC 2011 conference. An extended abstract in Proceedings of the the 22nd International Symposium on Algorithms and Computation, (ISAAC 2011), Yokohama, Japan, Vol. 7074 of LNCS, Springer, pp. 230-239.

[87] A. Dumitrescu and Cs. D. Tóth, Packing anchored rectangles, Combinatorica, to appear. A preliminary version in Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms, (SODA 2012), Kyoto, Japan, January 2012. Also available on arxiv.

[88] A. Dumitrescu, G. Rote, and Cs. D. Tóth, Monotone paths in planar convex subdivisions. An extended abstract in Proceedings of the 18th Annual International Computing and Combinatorics Conference, (COCOON 2012), Sydney, Australia, August 2012; Vol.7434 of LNCS, pp. 240-251. A preliminary short version in Abstracts of the 21st Fall Workshop on Computational Geometry (FWCG 2011), November 2011.

[89] A. Dumitrescu and M. Jiang, Maximal empty boxes amidst random points, Combinatorics, Probability and Computing, 22 (2013), 477-498. A preliminary version in Proceedings of the 16th International Workshop on Randomization and Computation, (RANDOM 2012), MIT, Boston, August 2012; Vol. 7408 of LNCS, pp. 529-540.

[90] A. Dumitrescu, S. Har-Peled, and Cs. D. Tóth, Minimum convex partitions and maximum empty polytopes, Journal of Computational Geometry, 5(1), 2014, 86-103. An extended abstract in Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012), Helsinki, Finland, July 2012, Vol. 7357 of LNCS, pp. 213-224. Also available on arxiv.

[91] A. Dumitrescu, D. Gerbner, B. Keszegh, and Cs. D. Tóth, Covering paths for planar point sets, Discrete & Computational Geometry, 51(2), 2014, 462-484. Also in Proceedings of the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, June 4-7, 2013, Veszprém, Hungary. A preliminary version in Proceedings of the 20th International Symposium on Graph Drawing, (GD 2012), Redmond, Washington, Sept. 2012, Vol. 7704 of LNCS, pp. 303-314.

[92] A. Dumitrescu, Metric inequalities for polygons, Journal of Computational Geometry, 4 (2013), 79-93.

[93] A. Dumitrescu and M. Jiang, Disjoint empty disks supported by a point set, Journal of Geometry, 2013; DOI 10.1007/s00022-013-0160-8. Also available on arxiv.

[94] A. Dumitrescu, Computational Geometry Column 53, SIGACT News Bulletin, 43(2), June 2012, 78-83.

[95] A. Dumitrescu and M. Jiang, Systems of distant representatives in Euclidean space. An extended abstract in Proceedings of the 29th Annual Symposium on Computational Geometry, (SOCG 2013), Rio de Janeiro, Brazil, June 2013.

[96] A. Dumitrescu and M. Jiang, On the approximability of covering points by lines and related problems, manuscript, 2013. Also available on arxiv.

[97] A. Dumitrescu and Cs. D. Tóth, The traveling salesman problem for lines, balls and planes. An earlier version in Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms, (SODA 2013), New Orleans, January 2013. Also available on arxiv.

[98] A. Dumitrescu and Cs. D. Tóth, On the total perimeter of homothetic convex bodies in a convex container, manuscript, 2014. Also available on arxiv. A preliminary version in Proceedings of the 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, (APPROX 2013), Berkeley, CA, August 2013. A short version "Packing disks that touch the boundary of a square" in Abstracts of the 22nd Fall Workshop on Computational Geometry (FWCG 2012), October 2012.

[99] A. Dumitrescu and Cs. D. Tóth, Computational Geometry Column 54, SIGACT News Bulletin, 43(4), December 2012, 90-97.

[100] A. Dumitrescu, J. Mitchell and P. Zylinski, The minimum guarding tree problem, Discrete Mathematics, Algorithms and Applications, 6(1) (2014). An earlier short version in Abstracts of the 29th European Workshop on Computational Geometry, (EuroCG 2013), Braunschweig, Germany, March 2013.

[101] A. Dumitrescu and M. Jiang, Computational Geometry Column 56, SIGACT News Bulletin, 44(2), June 2013.

[102] A. Dumitrescu, A. Ghosh, and Cs. D. Tóth, On fence patrolling by mobile agents, The Electronic Journal of Combinatorics, submitted. Also available on arxiv. A preliminary version in Proceedings of the 25th Canadian Conference on Computational Geometry, (CCCG 2013), Waterloo, Ontario, Canada, August 2013.

[103] A. Dumitrescu and M. Jiang, Computational Geometry Column 58, SIGACT News Bulletin, 44(4), December 2013.

[104] A. Dumitrescu and M. Jiang, The opaque square, Proceedings of the 30th Annual Symposium on Computational Geometry, (SOCG 2014), Kyoto, Japan, June 2014, p. 529. Also available on arxiv.

[105] K. Chen and A. Dumitrescu, Nonconvex cases for carpenter's rulers, Proceedings of the 7th International Conference on Fun with Algorithms, (FUN 2014), Lipari Island, Sicily, Italy, July 2014; Vol. 8496 of LNCS, pp. 89-99.

[106] A. Dumitrescu, A. Ghosh, and M. Hasan, On polygons cuttable with a circular saw, manuscript, 2014.

[107] A. Dumitrescu, M. Jiang, and Cs. D. Tóth, Computing opaque interior barriers à la Shermer, Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, (APPROX 2014), UPC Barcelona, Spain, Sept. 2014, to appear.

[108] A. Dumitrescu and Cs. D. Tóth, Computational Geometry Column 59, SIGACT News Bulletin, 45(2), June 2014.

[109] A. Dumitrescu and Cs. D. Tóth, Covering grids by trees , Proceedings of the 26th Canadian Conference on Computational Geometry, (CCCG 2014), Halifax, Nova Scotia, Canada, August 2014, to appear.

[110] K. Chen and A. Dumitrescu, Select with groups of 3 or 4 takes linear time, manuscript, 2014.

[111] A. Dumitrescu and Cs. D. Tóth, Binary space partitions , essay in Encyclopedia of Algorithms, Ming-Yang Kao (editor), Springer, 2014, to appear.

[112] A. Dumitrescu and Cs. D. Tóth, Convex polygons and monotone paths in geometric triangulations, manuscript, 2014.


Last update: July 2014