Adrian Dumitrescu
 Professor of Computer Science
 University of WisconsinMilwaukee
 3200 N. Cramer Street
 Milwaukee, WI 53211
 USA
 Phone: 4142294265
 dumitres[at)u w m(dot]e d u



DIGITAL DRAWINGS
AND COMPOSITIONS
PICTURES FROM
AN EXHIBITION
Recent Public Appearences, Inside/Outside Jobs, etc.


The 23rd Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2012),
Kyoto, January 1719, 2012.


The 30th Annual Symposium on Computational Geometry (SoCG 2014),
Kyoto, June 811, 2014.

 Member on the Program Committee of the
32nd International
Symposium on Theoretical Aspects of Computer Science (STACS 2015),
March 47, 2015, Munich, Germany.
 Member on the Program Committee of the
26th International Symposium on Algorithms and Computation (ISAAC 2015)
December 911, 2015, Nagoya, Japan.

Mathematical Art Works:
Recursive construction for sliding disks,
SIGMAAARTS Exhibition of Mathematical Art,
held as part of the AMSMAA Joint Mathematics Meetings,
Washington, DC, January 58, 2009.
Arrangement (2),
Exhibition of Mathematical Art,
held as part of the AMSMAA Joint Mathematics Meetings,
San Francisco, California, January 1316, 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
(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 CCF0444188 (2005  2011).
NSF grant DMS 1001667 (20102014).
Former PhD Students:
 Anirban Ghosh (PhD dissertation: April 8, 2016)
Current PhD Students:
Note:
If you are a student interested in doing
research under my supervision, you need to:
1. take at least one of the classes I am teaching.
2. read at least one of my papers to be able to discuss it.
3. after having done 1 and 2 above, you can approach me in
this regard.
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  June 2007: Assistant Professor of Computer Science
June 2007  August 2015: Associate Professor of Computer Science
Since Aug. 2015: Professor of Computer Science,
CS Dept., University of WisconsinMilwaukee
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, Fall
2015.
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,
Spring 2015.
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,
Fall 2015.
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
SSIMSI boards,
The Second Symposium on Automated Testing,
(TETA '83), Cluj, 1983 and in
AMC, vol. 46, Editura Tehnica, Bucharest, 1984, 5157.
[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,
(SAII5), 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,
(SAII6), Bucharest, 1985, vol. 2.
[5]
A. Dumitrescu,
On two lower bound constructions,
Eleventh Canadian Conference on Computational Geometry,
1999 (CCCG '99), 111114.
[6]
A. Dumitrescu,
Planar sets with few empty convex polygons,
Studia Scientiarum Mathematicarum Hungarica,
36(12), 2000, 93109; an extended abstract in
Proceedings of the Tenth Canadian Conference
on Computational Geometry, 1998 (CCCG '98), 1415.
[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(13), 2000, 183195.
[8]
A. Dumitrescu and R. Kaye,
Matching colored points in the plane: some new results,
Computational Geometry: Theory and Applications,
19(1), 2001, 6985.
[9]
A. Dumitrescu, B. Gärtner, S. Pedroni and E. Welzl,
Enumerating triangulation paths,
Computational Geometry: Theory and Applications,
20(12), 2001, 312.
Special issue of selected papers from CCCG '00.
An extended abstract in
Proceedings of the Twelfth Canadian Conference on Computational
Geometry, 2000 (CCCG '00), 233238.
[10]
A. Dumitrescu and W. Steiger,
Spacetime tradeoffs for some ranking and searching queries,
Information Processing Letters,
79(5), 2001, 237241.
[11]
A. Dumitrescu and G. Tóth,
Ramseytype results for unions of comparability graphs,
Graphs and Combinatorics, 18(2), 2002, 245251.
A preliminary version in
Proceedings of the Eleventh Canadian Conference on Computational
Geometry, 1999 (CCCG '99), 178181.
[12]
A. Dumitrescu and J. Pach,
Partitioning colored point sets into monochromatic parts,
International Journal of Computational Geometry
& Applications, 12(5), 2002, 401412.
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, 264275.
[13]
A. Dumitrescu,
On the maximum multiplicity of some
extreme geometric configurations in the plane,
Geombinatorics, 12(1), 2002, 514;
(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, 135159.
Special issue with selected papers from SODA'01.
An extended abstract in
Proceedings of the Twelfth ACMSIAM Symposium on Discrete Algorithms,
January 2001 (SODA '01), 3847.
[15]
A. Dumitrescu,
Efficient algorithms for generation of combinatorial covering suites,
Proceedings of the the 14th Annual International Symposium on
Algorithms and Computation (ISAAC '03),
Lecture Notes in Computer Science, Vol. 2906, 2003, 300308.
[16]
C. Cheng, A. Dumitrescu and P. Schroeder,
Generating small combinatorial test suites to cover inputoutput
relationships,
Proceedings of the Third International Conference on Quality
Software (QSIC '03),
Dallas, November 2003, 7682.
[17]
A. Dumitrescu, J. Mitchell and M. Sharir,
Binary space partitions for axisparallel segments, rectangles,
and hyperrectangles,
Discrete & Computational Geometry, 31(2), 2004, 207227.
A preliminary version in
Proceedings of the Seventeenth Annual Symposium on Computational
Geometry, June 2001 (SOCG'01), 141150.
[18]
A. Dumitrescu and S. Guha,
Extreme distances in multicolored point sets ,
Journal of Graph Algorithms and Applications,
8(1), 2004, 2738. 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, 1425.
[19]
A. Dumitrescu, I. Suzuki and M. Yamashita,
Formations for fast locomotion of metamorphic robotic systems,
International Journal of Robotics Research, 23(6), 2004, 583593.
A preliminary version in
Proceedings of the 2002 IEEE International Conference on Robotics
and Automation, (ICRA '02), Washington, May 2002, 123128.
[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, 409418.
[21]
A. Dumitrescu,
The cost of cutting out convex ngons,
Discrete Applied Mathematics, 143(13), 2004, 353358.
[22]
A. Dumitrescu,
An approximation algorithm for cutting out convex polygons,
Computational Geometry: Theory and Applications,
29(3), 2004, 223231.
A preliminary version in
Proceedings of the Fourteenth ACMSIAM Symposium on Discrete
Algorithms (SODA '03), January 2003, 823827.
[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 6774.
[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, 162165.
[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 155166.
[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, 5969.
A preliminary version in
Proceedings of the 10th Spanish Workshop on
Computational Geometry, Sevilla, June 2003, 4450.
[27]
A. Dumitrescu,
Monotone paths in line arrangements with a small number of directions,
Discrete & Computational Geometry, 33, 2005, 687697.
[28]
A. Dumitrescu,
On some monotone path problems in line arrangements,
Computational Geometry: Theory and Applications,
32, 2005, 1325.
A preliminary version in
Proceedings of the Sixteenth Canadian Conference on Computational
Geometry, (CCCG '04), August 2004, 200203.
[29]
A. Dumitrescu,
A remark on the ErdösSzekeres theorem,
American Mathematical Monthly, 112(12), 2005, 921924.
A preliminary version in
Proceedings of the Sixteenth Canadian Conference on Computational
Geometry, (CCCG '04), August 2004, 23.
[30]
A. Dumitrescu and J. Pach,
Pushing squares around,
Graphs and Combinatorics, 22(1), (2006), 3750.
A preliminary version in
Proceedings of the 20th Annual Symposium on Computational Geometry,
(SOCG'04), NY, June 2004, 116123.
[31]
A. Dumitrescu,
On distinct distances from a vertex of a convex polygon,
Discrete & Computational Geometry,
36, 2006, 503509.
Special issue with selected papers from SOCG '04.
An extended abstract in
Proceedings of the 20th Annual Symposium on Computational Geometry,
(SOCG'04), NY, June 2004, 5759.
[32]
G. Calinescu, A. Dumitrescu, H. Karloff and PengJun Wan,
Separating points by axisparallel lines,
International Journal of Computational Geometry
& Applications, 15(6), 2005, 575590.
Special issue with selected papers from CCCG '04.
[33]
A. Dumitrescu, A. EbbersBaumann, 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, 1638.
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, 244255.
[34]
S. Bereg, A. Dumitrescu and J. Pach,
Sliding disks in the plane,
International Journal of Computational Geometry
& Applications, 18(5), 2008, 373387.
A preliminary version in
Proceedings of Japan Conference on Discrete and Computational
Geometry, (JCDCG '04), October 2004, vol. 3742 of LNCS, pp. 3747.
[35]
S. Bereg and A. Dumitrescu,
The lifting model for reconfiguration,
Discrete & Computational Geometry,
35(4), 2006, 653669.
A preliminary version in
Proceedings of the 21st Annual Symposium on Computational Geometry,
(SOCG '05), Pisa, Italy, June 2005, 5562.
[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, 613618.
[37]
G. Calinescu, A. Dumitrescu and J. Pach,
Reconfigurations in graphs and grids,
SIAM Journal on Discrete Mathematics, 22(1), 2008, 124138.
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, 262273.
[38]
A. Dumitrescu and Cs. D. Tóth,
On the number of tetrahedra with minimum, unit, and distinct
volumes in threespace,
Combinatorics, Probability and Computing, 17(2), 2008, 203224.
A preliminary version in
Proceedings of the 18th ACMSIAM Symposium on Discrete Algorithms,
(SODA '07), New Orleans, January 2007, ACM Press, 11141123.
[39]
A. Dumitrescu and Cs. D. Tóth,
Light orthogonal networks with constant geometric dilation,
Journal of Discrete Algorithms, 7, 2009, 112129.
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, 175187.
[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, 513532.
A preliminary version in
Proceedings of the 23rd Annual Symposium on Computational Geometry,
(SOCG '07), Gyeongju, SouthKorea, June 2007, 4655.
[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. 119129.
[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 523542.
[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, 11771198.
An extended abstract in
Proceedings of the 24th Annual Symposium on Computational Geometry,
(SOCG '08), College Park, Maryland, USA, June 2008, 208217.
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, 220235.
A preliminary version in
Proceedings of the 23rd Annual Symposium on Computational Geometry,
(SOCG '07), Gyeongju, SouthKorea, June 2007, 102111.
[45]
A. Dumitrescu and G. Xu,
On two representation problems with infinite multiplicity,
JP Journal of Algebra, Number Theory and Applications,
9(2), 2007, 215236.
[46]
A. Dumitrescu,
On distinct distances and λfree point sets,
Discrete Mathematics, 308 (2008), 65336538.
[47]
A. Dumitrescu and Cs. D. Tóth,
Analysis of two sweepline algorithms
for constructing spanning trees and Steiner trees,
Journal of Universal Computer Science,
13(11), 2007, 16151627.
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, 627652.
A preliminary version in
Proceedings of the 19th ACMSIAM Symposium on Discrete Algorithms
(SODA '08), San Francisco, January 2008, ACM Press, 581590.
[49]
A. Dumitrescu and Cs. D. Tóth,
On stars and Steiner stars,
Proceedings of the 19th ACMSIAM Symposium on Discrete Algorithms
(SODA '08), San Francisco, January 2008, ACM Press, 12331240.
[50]
A. Dumitrescu and G. Xu,
On a query algorithm for a divisibility problem,
Communications in Computer Algebra,
41(4), 2007, 122125.
[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(67), 2009, 617626. 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, 201206.
[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, 105118.
[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,
Visionbased pursuitevasion in a grid,
SIAM Journal on Discrete Mathematics, 24(3), 2010, 11771204.
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. 5364.
[55]
S. Bereg, A. Dumitrescu and M. Jiang,
On covering problems of Rado,
Algorithmica, 57, 2010, 538561.
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. 294305.
[56]
A. Dumitrescu,
On distinct distances among points in general position
and other related problems,
Periodica Mathematica Hungarica, 57(2), 2008, 165176.
A preliminary version in
Proceedings of the 20th Canadian Conference on Computational
Geometry, (CCCG 2008), 6770.
[57]
A. Dumitrescu and M. Jiang,
Monochromatic simplices of any volume,
Discrete Mathematics, 310, 2010, 956960.
A preliminary version in
Proceedings of the 20th Canadian Conference on Computational
Geometry, (CCCG 2008), 7174.
[58]
A. Dumitrescu and M. Jiang,
Sweeping points, Algorithmica, 60(3), 2011, 703717.
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. 6376.
[59]
A. Dumitrescu, Cs. D. Tóth and G. Xu,
On stars and Steiner stars,
Discrete Optimization, 6(3), 2009, 324332.
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 ACMSIAM 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
FermatWeber center of a planar convex body,
Discrete Optimization, 8(3), 2011, 417427.
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, 91109.
[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, 191202. 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. 254265.
[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. 131142.
[64]
A. Dumitrescu and Cs. D. Tóth,
Long noncrossing configurations in the plane,
Discrete & Computational Geometry, 44(4), 2010, 727752.
A preliminary version in
Proceedings of the 27th International Symposium on Theoretical
Aspects of Computer Science,
(STACS 2010), Nancy, France, March 2010, pp. 299310.
[65]
A. Dumitrescu and M. Jiang,
The forest hiding problem,
Discrete & Computational Geometry, 45, 2011, 529552.
A preliminary version in
Proceedings of the 21st ACMSIAM Symposium on Discrete Algorithms,
(SODA 2010), Austin, Texas, Jan. 2010, pp. 15661579.
[66]
A. Dumitrescu,
Approximate Euclidean Ramsey theorems,
Journal of Computational Geometry, 2(1), 2011, 1629.
A preliminary version in
Proceedings of the 22nd Canadian Conference on Computational
Geometry, (CCCG 2010), Winnipeg, Manitoba, Canada, August 2010,
pp. 131134.
[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. 314.
[68]
A. Dumitrescu and J. Pach,
Minimum clique partition in unit disk graphs,
JCCGG 2009 special issue of Graphs and Combinatorics,
27(3), 2011, 399411.
[69]
A. Dumitrescu and M. Jiang,
On the largest empty axisparallel box amidst n points,
Algorithmica, 66(2), 2013, 225248.
Online first, March 2012; DOI 10.1007/s0045301296355.
Also available on arxiv.
[70]
A. Dumitrescu and M. Jiang,
Dispersion in disks,
Theory of Computing Systems, 51(2), 2012, 125142;
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. 311322.
[71]
A. Dumitrescu, J. Pach and G. Tóth,
A note on blocking visibility between points,
Geombinatorics, 19(1), 2009, 6773.
[72]
A. Dumitrescu and M. Jiang,
Minimumperimeter intersecting polygons,
Algorithmica, 63(3), 2012, 602615.
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, 433445.
[73]
A. Dumitrescu,
Going around in circles,
Computational Geometry: Theory and Applications,
45 (2012), 370381.
[74]
A. Dumitrescu and E. Hilscher,
On convexification of polygons by pops,
Discrete Mathematics, 310, 2010, 25422545.
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, 365377.
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. 257260.
[78]
A. Dumitrescu and Cs. D. Tóth,
Watchman tours for polygons with holes,
Computational Geometry: Theory and Applications,
45 (2012), 326333.
A preliminary version in
Proceedings of the 22nd Canadian Conference on Computational
Geometry, (CCCG 2010), Winnipeg, Manitoba, Canada, August 2010,
pp. 113116.
[79]
A. Dumitrescu and M. Jiang,
Constrained kcenter and movement to independence,
Discrete Applied Mathematics, 159(8), 2011, 859865.
A preliminary version in
Proceedings of the 22nd Canadian Conference on Computational
Geometry, (CCCG 2010), Winnipeg, Manitoba, Canada, August 2010,
pp. 233236.
[80]
A. Dumitrescu, M. Jiang and J. Pach,
Opaque sets,
Algorithmica, 69, 2014, 315334.
Online first, December 2012; DOI 10.1007/s0045301297352.
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, 194205.
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, 802826.
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. 220229.
A short version in Abstracts of the 20th Fall Workshop on
Computational Geometry (FWCG 2010), October 2930, 2010.
[83]
A. Dumitrescu and M. Jiang,
Sweeping an oval to a vanishing point,
Discrete Applied Mathematics, 159(14), 2011, 14361442.
A short version in
Proceedings of the XIV Spanish Meeting on Computational Geometry,
(EGC 2011), June 2011, pp. 5962. 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, 527538. 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. 3647.
[86]
A. Dumitrescu and M. Hasan,
Cutting out polygons with a circular saw,
International Journal of Computational Geometry
& Applications, 23(2), 2013, 127139.
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. 230239.
[87]
A. Dumitrescu and Cs. D. Tóth,
Packing anchored rectangles,
Combinatorica, 35(1), 2015, 3961.
A preliminary version in
Proceedings of the 23rd ACMSIAM 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. 240251.
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), 477498.
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. 529540.
[90]
A. Dumitrescu, S. HarPeled, and Cs. D. Tóth,
Minimum convex partitions and maximum empty polytopes,
Journal of Computational Geometry, 5(1), 2014, 86103.
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. 213224.
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, 462484.
Also in
Proceedings of the 8th JapaneseHungarian Symposium
on Discrete Mathematics and Its Applications,
June 47, 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. 303314.
[92]
A. Dumitrescu,
Metric inequalities for polygons,
Journal of Computational Geometry,
4 (2013), 7993.
[93]
A. Dumitrescu and M. Jiang,
Disjoint empty disks supported by a point set,
Journal of Geometry, 2013; DOI 10.1007/s0002201301608.
Also available on arxiv.
[94]
A. Dumitrescu,
Computational Geometry Column 53,
SIGACT News Bulletin, 43(2), June 2012, 7883.
[95]
A. Dumitrescu and M. Jiang,
Systems of distant representatives in Euclidean space,
Journal of Combinatorial Theory, Ser. A, 134 (2015), 3650.
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), 703717.
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:143:29.
Preprint available on arxiv.
An earlier version in
Proceedings of the 24th ACMSIAM 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, 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, 9097.
[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. 8999.
[106]
A. Dumitrescu, A. Ghosh, and M. Hasan,
On collections of polygons cuttable with a segment saw,
Discrete Applied Mathematics, to appear.
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. 5868.
[107]
A. Dumitrescu, M. Jiang, and Cs. D. Tóth,
Computing opaque interior barriers à la Shermer,
SIAM Journal on Discrete Mathematics, 29(3), 2015, 13721386.
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]
K. Chen and A. Dumitrescu,
Select with groups of 3 or 4,
Proceedings of the 29th International Workshop on Algorithms
and Data Structures, (WADS 2015), Victoria, Canada, August 2015,
LNCS 9214, Springer, 2015, pp. 189199;
also available on arxiv.
[111]
A. Dumitrescu and Cs. D. Tóth,
Binary space partitions ,
essay in Encyclopedia of Algorithms,
MingYang Kao (editor), Springer, Feb. 2015.
[112]
A. Dumitrescu, M. Löffler, A. Schulz, and Cs. D. Tóth,
Counting carambolas,
Graphs and Combinatorics, 32(3), 2016, 923942;
also available on arxiv.
[113]
A. Dumitrescu and Cs. D. Tóth,
Convex polygons in geometric triangulations,
Combinatorics, Probability and Computing, to appear;
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. 289300.
[114]
A. Dumitrescu and M. Jiang,
Computational Geometry Column 60,
SIGACT News Bulletin, 45(4), December 2014.
[115]
A. Dumitrescu and M. Jiang,
Minimum rectilinear Steiner tree of n points in the unit square,
Computational Geometry: Theory and Applications,
to appear.
[116]
B. Ábrego, A. Dumitrescu, S. Fernández, and Cs. D. Tóth,
Computational Geometry Column 61,
SIGACT News Bulletin, 46(2), June 2015.
[117]
A. Dumitrescu and Cs. D. Tóth,
Constantfactor approximation for TSP with disks,
to appear in the volume
Journey Through Discrete Mathematics. A Tribute to Jiri Matousek.
Preprint 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, 89110.
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,
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, to appear.
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,
A selectable sloppy heap,
manuscript, 2016; also available on arxiv.
[123]
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.
[124]
A. Dumitrescu and M. Jiang,
Perfect vector sets, properly overlapping partitions, and largest empty box,
manuscript, 2016; also available on arxiv.
[125]
A. Dumitrescu,
Computational Geometry Column 64,
SIGACT News Bulletin, 47(4), December 2016.
[126]
A. Dumitrescu,
Distinct distances and arithmetic progressions,
manuscript, 2017.
[127]
A. Dumitrescu and Cs. D. Tóth,
A problem on track runners,
Proceedings of the 29th Canadian Conference on Computational
Geometry, (CCCG 2017), Ottawa, Ontario, Canada, July 2017; to appear.
[128]
A. Dumitrescu,
On the shortest separating cycle,
Proceedings of the 29th Canadian Conference on Computational
Geometry, (CCCG 2017), Ottawa, Ontario, Canada, July 2017; to appear.
[129]
K. Chen and A. Dumitrescu,
On the longest spanning tree with neighborhoods,
manuscript, 2017.
Last update: June 2017