Adrian Dumitrescu

Associate Professor of Computer Science
University of Wisconsin-Milwaukee
3200 N. Cramer Street
Milwaukee, WI 53211
USA
Phone: 414-229-4265
Fax: 414-229-2769
ad(at)cs(dot)uwm(dot)edu

Recent awards:

DIMACS award for research support, 1999
DIMACS fellowship, 1999
NSF CAREER award, 2005
Graduate School/UWM Foundation research award, 2006

Editor 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 CAREER grant CCF-0444188.

Open PhD Position (posted: April 2009):

1-2 Research assistantships are available for PhD Students. Financial support is available. Check here for more details.

Open PostDoc Position (posted: May 2009):

A PostDoc position is available. General research area: Combinatorial Problems, Geometry and Algorithms. Check here for more details.

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 Sat. Dec. 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.
Data Structures and Algorithms (CS 535): Spring 2003, Fall 2003, Spring 2004, Spring 2005, Fall 2005.
Analysis of Algorithms (CS 704): Spring 2001, Spring 2002, Fall 2002, Spring 2003, Fall 2004, Spring 2006, Fall 2007.
Computational Geometry (CS 714): Fall 2003, Fall 2004, Fall 2006.
Randomized Algorithms and Pseudorandom Numbers(CS 805): Fall 2005, Spring 2007.

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:

[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, to appear. 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, to appear. 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.

[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, to appear. 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, to appear; 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, to appear. 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, to appear.

[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. 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, to appear; 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, Proceedings of the 20th Canadian Conference on Computational Geometry, (CCCG 2008), 71-74.

[58] A. Dumitrescu and M. Jiang: Sweeping points, 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, to appear; 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 and Cs. D. Tóth: New bounds on the average distance from the Fermat-Weber center of a planar convex body, manuscript, 2008. An earlier 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, to appear.

[62] A. Dumitrescu and M. Jiang: On reconfiguration of disks in the plane and other related problems. A short version in: Proceedings of the 23rd International Workshop on Algorithms and Data Structures, (WADS '09), Banff, August 2009; to appear.

[63] A. Dumitrescu and M. Jiang: Piercing translates and homothets of a convex body. A short version in: Proceedings of the 17th Annual European Symposium on Algorithms, (ESA '09), Copenhagen, Sept. 2009; to appear.

[64] A. Dumitrescu and Cs. D. Tóth: Long non-crossing configurations in the plane; manuscript, 2008.

[65] A. Dumitrescu and M. Jiang: The forest hiding problem; manuscript, 2008.

[66] A. Dumitrescu: Approximate Euclidean Ramsey theorems; manuscript, 2008.

[67] A. Dumitrescu and J. Pach: Minimum clique partition in unit disk graphs; manuscript, 2009.

[68] A. Dumitrescu and M. Jiang: On the largest empty axis-parallel box amidst n points; manuscript, 2009.

[69] A. Dumitrescu, J. Pach and G. Tóth, Drawing Hamiltonian cycles with no large angles; manuscript, 2009.

[70] A. Dumitrescu and M. Jiang: Dispersion in unit disks; manuscript, 2009.