Home Bookmarks Search (Re)search CG Papers

Papers

"Wir müssen wissen, wir werden wissen" -- David Hilbert
(We must know, we shall know)
Notes, Other publications, Talks.

A List of my Survey:

    Geometric Approximation via Coresets, with P.K. Agarwal, and Kasturi R. Varadarajan.

Manuscripts

Papers in Conferences

   
  1. "Range Medians", with S. Muthukrishnan. To appear in ESA 08.
  2. "On Embeddings of Moving Points in Euclidean Space", with P.K. Agarwal and H. Yu. To appear in SoCG 07.
  3. "Maximum Margin Coresets for Active and Noise Tolerant Learning", with D. Roth and D. Zimak. In IJCAI 07.
  4. "Coresets for Discrete Integration and Clustering". In FSTTCS 06.
  5. "Approximation Algorithms for Two Optimal Location Problems in Sensor Networks", with A. Efrat and J. S. B. Mitchell. In Broadnets 2005.
  6. "A Time-Optimal Delaunay Refinement Algorithm in Two Dimensions", with A. Ungor. In SoCG 05.
  7. "Coresets for k-Means and k-Median Clustering and their Applications", with S. Mazumdar. In STOC 04.
  8. "Constraint Classification: A New Approach to Multiclass Classification and Ranking ", with D. Roth and D. Zimak, in NIPS 2002.
  9. "Projective Clustering in High Dimensions using Coresets", with K. Varadarajan, in SoCG 2002.
  10. "Approximate Clustering via Coresets", with M. Badoiu and P. Indyk, in STOC 2002.
  11. "On generalization bounds, projection profile, and margin distribution", with A. Garg and D. Roth. In ICML 2002.
  12. "A Replacement for Voronoi Diagrams of Near Linear Size", in FOCS 01.
  13. "A Practical Approach for Computing the Diameter of a Point-Set ", in SoCG 01.
   Submitted to a journal:
   
  1. "Relative eps-Approximations in Geometry", with M. Sharir. To appear in SoCG 07 (as a merged paper).
  2. "On Approximating the Depth and Related Problems", with B. Aronov. In SODA 05.
   No journal version is planned:
   
  1. "No Coreset, No Cry". Appeared in FSTTCS 04.
  2. "Efficient Algorithms for Shared Camera Control", with V. Koltun, D. Song and K. Goldberg, in SoCG 03.
  3. "STAR-Tree: An Efficient Self-Adjusting Index for Moving Objects", with P.K. Agarwal and C.M. Procopiuc. In ALENEX 02.
  4. "When Crossings Count - Approximating the Minimum Spanning Tree", with P. Indyk, in SoCG 2000.
  5. "Occlusion Culling for Fast Walkthrough in Urban Areas". with Y. Wang and P.K. Agarwal. In Eurographics 01.
    Journal version appeared without me being involved:
   
  1. "Results on k-sets and j-facets via continuous motion arguments", with A. Andrzejak, B. Aronov, R. Seidel and E. Welzl, in SoCG '98.
  2. "Fly Cheaply: On the Minimum Fuel-Consumption Problem", with A. Efrat, in SoCG '98.

Papers in Journals

   

Did not appear yet

  1. "Hausdorff Distance under Translation for Points, Disks, and Balls", with P.K. Agarwal, M. Sharir and Y. Wang, in SoCG 03. To appear in TALG.
  2. "Robust Shape Fitting via Peeling and Grating Coresets, with P.K. Agarwal and H. Yu. In SODA 06. To appear in DCG.
  3. "The Orienteering Problem in the Plane Revisited", with Ke Chen. In SoCG 06. To appear in SICOMP.
   

Published

  1. "On Finding a Guard that Sees Most and a Shop that Sells Most", with O. Cheong and A. Efrat. DCG 37 (4): 545-563 (2007). Also in SODA 04.
  2. "Smaller Coresets for k-Median and k-Means Clustering", with A. Kushal. DCG 37 (1): 3-19, 2007. Also on SoCG 05.
  3. "How to Get Close to the Median Shape". In CGTA 36 (1): 39-51, 2007. Also in SoCG 06.
  4. "On the Least Median Square Problem", with J. Erickson and D. Mount. In DCG 36 (4): 593-607, 2006. Also in SoCG 04.
  5. "Fast Construction of Nets in Low Dimensional Metrics, and Their Applications", with M. Mendel. In SICOMP 35: (5) 1148--1184, 2006. Also in SoCG 05.
  6. "On the Fermat-Weber Center of a Convex Object", with P. Carmi, and M. J. Katz. In CGTA 32: (3) 188-195, 2005.
  7. "On Conflict-Free Coloring of Points and Simple Regions in the Plane", with S. Smorodinsky. In DCG 34 (1):40-70, 2005, also in SoCG 03.
  8. "Near-Linear Time Approximation Algorithms for Curve Simplification in Two and Three dimensions", with P.K. Agarwal, N. Mustafa, and Y. Wang, in ESA 02, 29-41. In Algorithmica, 42:203-219, 2005.
  9. "Generalization Bounds for the Area Under the ROC Curve", with S. Agarwal, T. Graepel, R. Herbrich, and Dan Roth. J. Mach. Learn. Research, 6:393--425, Apr 2005.
    Based partially on "A Uniform Convergence Bound for the Area Under the ROC Curve", with S. Agarwal and D. Roth. In AISTAT 05.
  10. "Geographic Quorum Systems Approximations", with P. Carmi, S. Dolev, M. J. Katz, and M. Segal. In Algorithmica, 41 (4): 233--244, 2005.
  11. "How fast is the k-means Method?", with B. Sadri. In Algorithmica, 41(3):185--202, 2005. Also in SODA 05.
  12. "Approximating k-Hop Minimum-Spanning Trees, with Ernst Althaus, Stefan Funke, Jochen Konemann, Edgar A. Ramos, and Martin Skutella. In Oper. Res. Lett., 33(2):115--120, March 2005.
  13. "Fast Algorithms for Computing the Smallest k-Enclosing Disc", with S. Mazumdar. In Algorithmica, 41(3):147--157, 2005. Also in ESA 03.
  14. "Shape Fitting with Outliers", with Y. Wang, in SICOMP 33(2):269-285, 2004. Also in SoCG 03.
  15. "High-Dimensional Shape Fitting in Linear Time", with K. R. Varadarajan, in DCG 32 (2):269-288, 2004, also in SoCG 03.
  16. "Optimally Cutting a Surface into a Disk", with J. Erickson, in DCG 31 (1):37-59, 2004. Also in SoCG 2002.
  17. "The One-Round Voronoi Game", with O. Cheong, N. Linial, and J. Matousek, in DCG 31 (1):125-138, 2004. Also in SoCG 2002.
  18. "Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions", with P.K. Agarwal, M. de Berg, M.H. Overmars, M. Sharir and J. Vahrenhold, in CGTA 23:195--208 (2002), also in WADS 01.
  19. "Clustering motion", DCG 31 (4): 545--565, 2004, also in FOCS 01.
  20. "Approximating Extent Measure of Points with P.K. Agarwal and K. R. Varadarajan. In J. ACM, 51 (4): 606-635, 2004.
    Based on "Approximate Shape fitting via Linearization ", and "Maintaining the Approximate Extent Measures of Moving Points".
  21. "Computing the Penetration Depth of Two Convex Polytopes in 3D", with P.K. Agarwal, L.J. Guibas, A. Rabinovitch, and M. Sharir, in Nordic J. Comput. 3:(7), 227-240 (2000). Also in SWAT 2000.
  22. "Computing Approximate Shortest Paths on Convex Polytopes", with P.K. Agarwal, and M. Karia, in Algorithmica 33 (2), 227-242, 2002. Also in SoCG 2000.
  23. "Online Point Location in Planar Arrangements and Its Applications", with M. Sharir, in DCG 26 (1): 19-40, 2001. Also in SODA 01.
  24. "New Similarity Measures between Polylines with Applications to Morphing and Polygon Sweeping", with A. Efrat, L.J. Guibas, J.S.B. Mitchell, and T.M. Murali, in, DCG 28:535-569 (2002).
    Based on "Morphing between Polylines" and "Sweeping Simple Polygons with a Chain of Guards".
  25. "Routing with a clue", with A. Bremler and Y. Afek, in Trans. on Networking, 9(6):693--705, 2001. Also in SIGCOMM '99.
  26. "An experimental study of on-line methods for zone construction in arrangements of lines in the plane, in IJCGA, with D. Halperin, C, Linhart, and I. Hanniel.
    Also appeared as "On-line Zone Construction in Arrangements of Lines in the Plane", with Y. Aharoni, D. Halperin, I. Hanniel, C. Linhart, in WAE 99.
  27. "Taking a Walk in a Planar Arrangement", in SICOMP 30 (4) 1341-1367, 2000. Also in FOCS 99.
  28. "Approximation and Exact Algorithms for Minimum-Width Annuli and Shells ", with P.K. Agarwal, B. Aronov, and M. Sharir, in DCG 24(4): 687--705, 2000. Also in SoCG '99.
  29. "Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions", with G. Barequet, in J. Algorithms 38 (1): 91-109, 2001. Also in SODA 99.
  30. "Some Variants of Polygon Containment and Minimum Hausdorff Distance under Translation are 3sum-Hard", with G. Barequet, in IJCGA. Also in SODA 99.
  31. "Constructing Planar Cuttings in Theory and Practice". SICOMP 29 (6) 2016-2039, 2000. Also in SoCG '98.
  32. "Constructing Approximate Shortest Path Maps in Three Dimensions", in SICOMP, 28 (4), 1182-1197 (1999). Also in SoCG '98.
  33. "Approximate Shortest-Path and Geodesic Diameter on Convex Polytopes in Three Dimensions", in DCG, 21: 217-231 (1999). Also in SoCG '97.
  34. "An Output Sensitive Algorithm for Discrete Convex Hulls", CGTA, 10 (1998) 125-138. Also in SoCG '98.
  35. "Approximating Shortest Paths on a Convex Polytope in Three Dimensions", with P.K. Agarwal, M. Sharir, and K.R. Varadarajan. In J. ACM, 44 (1997), 567-584. Also in SoCG '96.
  36. "Multicolor Combination Lemma", in CGTA, 12:155-176 (1999). (Master thesis.)

PhD Thesis

Geometric Approximation Algorithms and Randomized Algorithms for Planar Arrangements.

Notes

Some other publications

   
  1. "Staying in the Middle: Exact and Approximate Medians in R1 and R2 for Moving Points", with P.K. Agarwal, M. de Berg, J. Gao, and L. J. Guibas. CCCG 05.
  2. "The complexity of a single face of a Minkowski sum", with T. M. Chan, B. Aronov, D. Halperin and J. Snoeyink, in CCCG 95, 91--96.

Conferences

  1. SoCG 07 - Gyeongju, South-Korea (2:45/139).
    SoCG 2006 - Sedona, Arizona (2:54/138).
    SoCG 2005 - Pisa, Italy (3:41:140)
    SoCG 2004 - New York City, USA (1:49:147)
    SoCG 2003 - San Diego, USA (5:42:118)
    SoCG 2002 - Barcelona (3:35/104).
    SoCG 2001 - Boston. (AT 1:14/35),
    SoCG 2000 - Hong Kong, (AT 1:16/50, TT 1:25/73)
    SoCG 1999 - Miami, Florida. (TT 1:27/61)
    SoCG 1998 - Minneapolis, Minnesota. (AT 2:19/53, TT 3:25/57)
    SoCG 1997 - Nice, France. (TT 1: 27/92)
    SoCG 1996 - Philadelphia, Pennsylvania. (1: 39/93)
  2. STOC 2004 - Chicago (1:71/273)
    STOC 2002 (1:91/287)
  3. FOCS 2001 - Las Vegas. (3:63/214),
    FOCS 1999 - New York City (1: 67/218)
  4. SIGCOMM '99 (1: 24/190)
  5. WAE 99 (1: 24/46)
  6. WADS 2001 (1:40/89)
  7. SWAT 2000
  8. SODA 2006 - Miami (1:135/432)
    SODA 2005 - Vancover (2:135/487)
    SODA 2004 - New Orleans (1:135/454)
    SODA 2001 (3:95/224).
    SODA 2000 (1:123/335),
    SODA 1999 (1 short, 1 long).
  9. AISTAT 05: (1:58/150)
  10. ALENEX 2002: (1:15/34)
  11. WADS 01: 1
  12. ESA 02:
    ESA 03: (1:46/119)
    ESA 06: (1:52/215)
  13. FSTTCS 04: (1:38/176)
    FSTTCS 06:
  14. Broadnets 2005: (1:49/100).

Journals

  1. JACM: 2
  2. SICOMP: 6
  3. DCG: 12
  4. TALG: 1
  6. CGTA: 4
  7. Nordic J. Comput.: 1
  8. Algorithmica: 4
  9. Trans. on Networking: 1
  10. J. Algorithms : 1
  11. ORL - Operation Research Letters

Coauthors that want to be linked from this page

  1. Dav Zimak
Last modified: Tue May 27 22:56:18 CDT 2008