Adrian Dumitrescu


Adrian Dumitrescu is a computer scientist and mathematician
with expertise in the fields of theory of algorithms, combinatorics,
and discrete and computational geometry.
He is a founder of AlgOrEsEArch.
He is a computer science professor,
formerly a faculty member at the University of Wisconsin-Milwaukee,
and held visiting positions at SUNY at Stony Brook (2000),
Rényi Institute of Mathematics of the Hungarian Academy of Sciences (2008),
Institut de Mathématiques, École Polytechnique Fédérale de Lausanne (2009),
and Université Libre de Bruxelles (2016).
He has written one book and about 250 papers.

Place of birth: Bucharest, Romania

PhD: Rutgers University, NJ

Academic advisor: William Steiger

Postdoctoral advisor: Joseph Mitchell

ad.dumitrescu\\At//G mAiL//d .o. t\\C oM//



DIGITAL DRAWINGS AND COMPOSITIONS

PICTURES AT AN EXHIBITION  See also here.




Public Appearences, Program Committees, etc.


Mathematical Art Works:

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


Awards:


Member on the Editorial Board of:

Algorithms (2008 - 2014)

Journal of Universal Computer Science (2008 - 2015)


Research Interests:

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


Research Grants:

NSF CAREER grant CCF-0444188 (2005 - 2011).
NSF grant DMS 1001667 (2010-2014).


Former PhD Students:


Other:

My Erdös number is 2.


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.




Books:

[1] Adrian Dumitrescu and Ke Chen, The Ape Book: Algorithmic Problems and Exercises, ISBN: 9798674163009, August 2020. (Available at amazon.com)


Papers:

Here are some other lists of my publications compiled by DBLP, Google Scholar, MathSciNet, and arXiv.

  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. Călinescu 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. Călinescu, 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. Călinescu, 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, Journal of Discrete Algorithms, 7, 2009, 112-129. 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, The Electronic Journal of Combinatorics, 19(2), 2012, 31-34. A preliminary version in 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. 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. 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, 47(4), 2014, 527-538. 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, 35(1), 2015, 39-61. 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, Journal of Combinatorial Theory, Ser. A, 134 (2015), 36-50. 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, Computational Geometry: Theory and Applications, 48 (2015), 703-717. Also available on arXiv.

  97. A. Dumitrescu and Cs. D. Tóth, The traveling salesman problem for lines, balls and planes, ACM Transactions on Algorithms, 12(3), 2016, 43:1-43:29. Preprint available on arXiv. An earlier version in Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms, (SODA 2013), New Orleans, January 2013.

  98. A. Dumitrescu and Cs. D. Tóth, On the total perimeter of homothetic convex bodies in a convex container, Beiträge zur Algebra und Geometrie, 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, 21(3), 2014, P3.4. 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, Theoretical Computer Science, 2015. Special issue with invited papers from the FUN 2014 conference. A preliminary version in 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 collections of polygons cuttable with a segment saw, Discrete Applied Mathematics, 228, (2017), 98-108. Special issue with selected papers from CALDAM 2015. A preliminary version in Proceedings of the International Conference on Algorithms and Discrete Applied Mathematics, (CALDAM 2015), IIT Kanpur, India, February 2015, Vol. 8959 of LNCS, pp. 58-68.

  107. A. Dumitrescu, M. Jiang, and Cs. D. Tóth, Computing opaque interior barriers à la Shermer, SIAM Journal on Discrete Mathematics, 29(3), 2015, 1372-1386. A preliminary version in Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, (APPROX 2014), UPC Barcelona, Spain, Sept. 2014, Leibniz International Proceedings in Informatics (LIPIcs) series, Schloss Dagstuhl.

  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.

  110. A. Dumitrescu and Cs. D. Tóth, Binary space partitions , essay in Encyclopedia of Algorithms, Ming-Yang Kao (editor), Springer, Feb. 2015.

  111. A. Dumitrescu, M. Löffler, A. Schulz, and Cs. D. Tóth, Counting carambolas, Graphs and Combinatorics, 32(3), 2016, 923-942; also available on arXiv.

  112. A. Dumitrescu and Cs. D. Tóth, Convex polygons in geometric triangulations, Combinatorics, Probability and Computing, 26(5), 2017, 641-659; also available on arXiv. A preliminary version in Proceedings of the 29th International Workshop on Algorithms and Data Structures, (WADS 2015), Victoria, Canada, August 2015, LNCS 9214, Springer, 2015, pp. 289-300.

  113. A. Dumitrescu and M. Jiang, Computational Geometry Column 60, SIGACT News Bulletin, 45(4), December 2014.

  114. A. Dumitrescu and M. Jiang, Minimum rectilinear Steiner tree of n points in the unit square, Computational Geometry: Theory and Applications, 68, 2018, 253-261.

  115. B. Ábrego, A. Dumitrescu, S. Fernandez, and Cs. D. Tóth, Computational Geometry Column 61, SIGACT News Bulletin, 46(2), June 2015.

  116. A. Dumitrescu and Cs. D. Tóth, Constant-factor approximation for TSP with disks, Journey Through Discrete Mathematics. A Tribute to Jiri Matousek, 2017. Preprint available on arXiv.

  117. K. Chen and A. Dumitrescu, Selection algorithms with small groups, International Journal of Foundations of Computer Science, Vol. 31, No. 3 (2020), 355--369. A preliminary version in Proceedings of the 29th International Workshop on Algorithms and Data Structures, (WADS 2015), Victoria, Canada, August 2015, LNCS 9214, Springer, 2015, pp. 189-199; also available on arXiv.

  118. A. Dumitrescu and A. Ghosh, Lower bounds on the dilation of plane spanners, International Journal of Computational Geometry & Applications, 26(2), 2016, 89-110. Preprint available on arXiv. A preliminary version in Proceedings of the International Conference on Algorithms and Discrete Applied Mathematics, (CALDAM 2016), Kerala, Thiruvananthapuram, India, February 2016, LNCS 9602.

  119. A. Dumitrescu and A. Ghosh, Lattice spanners of low degree. Discrete Mathematics, Algorithms and Applications, 8(3), 2016, article 1650051, 19 pages. Also available on arXiv. An earlier version (now obsolete) in Proceedings of the International Conference on Algorithms and Discrete Applied Mathematics, (CALDAM 2016), Kerala, Thiruvananthapuram, India, February 2016, LNCS 9602.

  120. K. Balas, A. Dumitrescu, and Cs. D. Tóth, Anchored rectangle and square packings, Discrete Optimization, 26, 2017, 131-162. A preliminary version in Proceedings of the 32nd Annual Symposium on Computational Geometry, (SOCG 2016), Boston, MA, June 2016, Leibniz International Proceedings in Informatics (LIPIcs) series, Schloss Dagstuhl; also available on arXiv.

  121. A. Dumitrescu and M. Jiang, On the number of maximum empty boxes amidst n points, Discrete & Computational Geometry, 59(3), 2018, 742-756. A preliminary version in Proceedings of the 32nd Annual Symposium on Computational Geometry, (SOCG 2016), Boston, MA, June 2016, Leibniz International Proceedings in Informatics (LIPIcs) series, Schloss Dagstuhl.

  122. A. Dumitrescu, R. Mandal, and Cs. D. Tóth, Monotone paths in geometric triangulations, manuscript, 2016; also available on arXiv. A preliminary version (now obsolete) in Proceedings of the 27th International Workshop on Combinatorial Algorithms, (IWOCA 2016), Helsinki, Finland, August 2016, LNCS 9843.

  123. A. Dumitrescu and M. Jiang, Perfect vector sets, properly overlapping partitions, and largest empty box, manuscript, 2016; also available on arXiv.

  124. A. Dumitrescu, Computational Geometry Column 64, SIGACT News Bulletin, 47(4), December 2016.

  125. A. Dumitrescu and Cs. D. Tóth, A problem on track runners, Computational Geometry: Theory and Applications, Vol. 68 (2020), 101611. Special issue of selected papers from CCCG 2017. A preliminary version in Proceedings of the 29th Canadian Conference on Computational Geometry, (CCCG 2017), Ottawa, Ontario, Canada, July 2017. Preprint available on arXiv.

  126. A. Dumitrescu, On the shortest separating cycle, Computational Geometry: Theory and Applications, Vol. 68 (2020), 101612. Special issue of selected papers from CCCG 2017. A preliminary version in Proceedings of the 29th Canadian Conference on Computational Geometry, (CCCG 2017), Ottawa, Ontario, Canada, July 2017.

  127. A. Dumitrescu, A selectable sloppy heap, Algorithms, 2019, 12(3), 58; doi: 10.3390/a12030058.

  128. A. Dumitrescu, Distinct distances and arithmetic progressions, Discrete Applied Mathematics, 256, 2019, 38-41.

  129. A. Dumitrescu and Cs. D. Tóth, Online unit clustering and unit covering in higher dimensions, Algorithmica, 84(5): 1213-1231, (2022). A preliminary version in Proceedings of the 15th Workshop on Approximation and Online Algorithms, (WAOA 2017), Vienna, Austria, Sept. 2017; in LNCS. Preprint available on arXiv.

  130. K. Chen and A. Dumitrescu, On the longest spanning tree with neighborhoods, Discrete Mathematics, Algorithms and Applications, 12(5), (2020), 2050067:1-2050067:16. A preliminary version in Proceedings of the 12th International Frontiers of Algorithmics Workshop, (FAW 2018), Guangzhou, China, May 2018; in LNCS. Preprint available on arXiv.

  131. K. Elbassioni and A. Dumitrescu, Computational Geometry Column 66, SIGACT News Bulletin, 48(4), December 2017.

  132. A. Dumitrescu, A. Ghosh, and Cs. D. Tóth, Online unit covering in Euclidean space, Theoretical Computer Science, Vol. 809, 2020, 218-230. Special issue with selected papers from COCOA 2018. A preliminary version in Proceedings of the 12th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2018), Atlanta, Georgia, December 2018, vol. 11346 of LNCS, pp. 609-623. Preprint available on arXiv.

  133. A. Dumitrescu, Distinct distances in planar point sets with forbidden 4-point patterns, Discrete Mathematics, 343(9), (2020), 111967.

  134. J-L de Carufel, A. Dumitrescu, W. Meulemans, T. Ophelders, C. Pennarun, Cs. D. Tóth, and S. Verdonschot, On convex polygons in Cartesian products, Journal of Computational Geometry, 11(2), 2020, 205--233. Special issue with selected papers from SOCG 2019. A preliminary version in Proceedings of the 34th Annual Symposium on Computational Geometry (SOCG 2019), Portland, OR, June 2019, Leibniz International Proceedings in Informatics (LIPIcs) series, Schloss Dagstuhl. A short version in Abstracts of EuroCG 2018, Berlin, Germany, March 2018. Preprint available on arXiv.

  135. A. Dumitrescu, A product inequality for extreme distances, Computational Geometry: Theory and Applications, 85 (2019) 101577. A preliminary version in Proceedings of the 34th Annual Symposium on Computational Geometry (SOCG 2019), Portland, OR, June 2019, Leibniz International Proceedings in Informatics (LIPIcs) series, Schloss Dagstuhl.

  136. A. Dumitrescu and R. Mandal, New lower bounds for the number of pseudoline arrangements, Journal of Computational Geometry, 11(1): 60-92, (2020). A preliminary version in Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, January 2019, pp. 410-425. Preprint available on arXiv.

  137. A. Dumitrescu, Finding a mediocre player, Discrete Applied Mathematics, 223: 15-24, (2021). A preliminary version in Proceedings of the 11th International Conference on Algorithms and Complexity (CIAC 2019), Rome, Italy, May 2019, in LNCS. Preprint available on arXiv.

  138. A. Dumitrescu, Computational Geometry Column 68, SIGACT News Bulletin, 49(4), December 2018,

  139. K. Chen, A. Dumitrescu, W. Mulzer, and Cs. D. Tóth, On the stretch factor of polygonal chains, SIAM Journal on Discrete Mathematics, 35(3): 1592-1614, (2021). A preliminary version in Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), August 2019, Aachen, Germany, Leibniz International Proceedings in Informatics (LIPIcs) series, Schloss Dagstuhl. Preprint available on arXiv.

  140. A. Dumitrescu and M. Jiang, Computational Geometry Column 69, SIGACT News Bulletin, 50(3), September 2019.

  141. A. Dumitrescu and Cs. D. Tóth, On the cover of the rolling stone, Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), Salt Lake City, January 2020.

  142. K. Chen and A. Dumitrescu, On Wegner's conjecture for axis-parallel rectangles, Discrete Mathematics, 343: 112091, (2020).

  143. K. Chen and A. Dumitrescu, Multiparty selection, Proceedings of the the 31st International Symposium on Algorithms and Computation} (ISAAC 2020), December 14-18, 2020, Hong Kong, China (Virtual Conference), Leibniz International Proceedings in Informatics (LIPIcs) series, Schloss Dagstuhl, vol. 181, pp. 42:1-42:13. Preprint available on arXiv.

  144. A. Dumitrescu, A. Ghosh, and Cs. D. Tóth, Sparse hop spanners for unit disk graphs, Computational Geometry: Theory and Applications, 100: 101808, (2022). A preliminary version in Proceedings of the the 31st International Symposium on Algorithms and Computation (ISAAC 2020), December 14-18, 2020, Hong Kong, China (Virtual Conference), Leibniz International Proceedings in Informatics (LIPIcs) series, Schloss Dagstuhl, vol. 181, pp. 57:1-57:17. Preprint available on arXiv.

  145. A. Dumitrescu and J. Tkadlec, Piercing all translates of a set of axis-parallel rectangles, Proceedings of the 32nd International Workshop on Combinatorial Algorithms (IWOCA 2021), Ottawa, Canada, July 2021, Vol. 12757 of LNCS, pp. 295-309, Springer, 2021. Preprint available on arXiv.

  146. A. Dumitrescu and J. Tkadlec, Lattice and non-lattice piercing of axis-parallel rectangles: exact algorithms and a separation result, manuscript, 2022. Preprint available on arXiv.

  147. A. Dumitrescu, The Dirac-Goodman-Pollack conjecture, Discrete & Computational Geometry, 2023, 1-15. Preprint available on arXiv.

  148. A. Dumitrescu and Cs. D. Tóth, Finding points in convex position in density-restricted sets, manuscript, 2022. Preprint available on arXiv.

  149. A. Dumitrescu, Peeling sequences, Mathematics, 10(22), 2022.

  150. A. Dumitrescu, Two-sided convexity testing with certificates, Proceedings of the 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, March 2023, Budapest, Hungary. Preprint available on arXiv.

  151. A. Dumitrescu and Cs. D. Tóth, Maximal distortion of geodesic diameters in polygonal domains, Proceedings of the 34th International Workshop on Combinatorial Algorithms (IWOCA 2023), June 2023, Tainan, Taiwan, vol. 13889 of LNCS. A preliminary version in Proceedings of the 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, March 2023, Budapest, Hungary. Preprint available on arXiv.

  152. A. Dumitrescu and A. Lingas, Finding small complete subgraphs efficiently, Proceedings of the 34th International Workshop on Combinatorial Algorithms (IWOCA 2023), June 2023, Tainan, Taiwan, vol. 13889 of LNCS.
    Best paper of IWOCA 2023.

  153. A. Dumitrescu and Cs. D. Tóth, Observation routes and external watchman routes, Proceedings of the 18th Algorithms and Data Structures Symposium, (WADS 2023), Montreal, Canada, Vol. 14079 of LNCS, pp. 401-415. Preprint available on arXiv.

  154. A. Dumitrescu and G. Tóth, Peeling sequences, Discrete & Computational Geometry, to appear. Preprint available on arXiv.

  155. A. Dumitrescu, Finding triangles or independent sets, manuscript, 2023. Preprint available on arXiv.

  156. J. Balogh, F. C. Clemen, and A. Dumitrescu, Almost congruent triangles, Discrete & Computational Geometry, to appear. Preprint available on arXiv.

  157. J. Balogh, F. C. Clemen, and A. Dumitrescu, On a traveling salesman problem for points in the unit cube, manuscript, 2023. Preprint available on arXiv.


Looking for open problems or ideas? Check here, or here.


Last update: December 2023