Sariel Har-Peled

Sariel Har-Peled

Auto-generated profile, based on publicly available information

Sariel Har-Peled

Department of Computer Science University of Illinois 201 N. Goodwin Avenue 61801 Urbana IL USA

Research Focus & Metrics

Academic Career Length

29Years (1998-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
7 March 2012 in Discrete & Computational Geometry
Verified
Journal Article
Closed access
PDF file
TCTimothy M. Chan
Timothy M. Chan
SHSariel Har-Peled
Sariel Har-Peled

12 December 2006 in Discrete & Computational Geometry
Verified
Journal Article
Closed access
PDF file
SHSariel Har-Peled
Sariel Har-Peled
AKAkash Kushal
Akash Kushal

1 January 2004 in Discrete & Computational Geometry
Verified
Journal Article
Open access
PDF file
JEJeff Erickson
Jeff Erickson
SHSariel Har-Peled
Sariel Har-Peled
We consider the problem of cutting a subset of the edges of a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or their total length. We show that this problem is NP-hard in general, even for manifolds without boundary and for punctured spheres. We also describe an algorithm with running time n O(g+k), where n is the combinatorial complexity, g is the genus, and k is the number of boundary components of the input surface. Finally, we describe a greedy algorithm that outputs a O(log2 g)-approximation of the minimum cut graph in O(g 2 n log n) time.

18 February 2010 in Discrete & Computational Geometry
Verified
Journal Article
Closed access
PDF file
SHSariel Har-Peled
Sariel Har-Peled
MSMicha Sharir
Micha Sharir

7 April 2005 in Discrete & Computational Geometry
Verified
Journal Article
Open access
PDF file
SHSariel Har-Peled
Sariel Har-Peled
SSShakhar Smorodinsky
Shakhar Smorodinsky
We study conflict-free colorings, where the underlying set systems arise in geometry. Our main result is a general framework for conflict-free coloring of regions with low union complexity. A coloring of regions is conflict-free if for any covered point in the plane, there exists a region that covers it with a unique color (i.e., no other region covering this point has the same color). For example, we show that we can conflict-free color any family of n pseudo-discs with O(log n) colors.

18 February 2012 in Discrete & Computational Geometry
Verified
Journal Article
Open access
PDF file
ADAnne Driemel
Anne Driemel
SHSariel Har-Peled
Sariel Har-Peled
CWCarola Wenk
Carola Wenk
We present a simple and practical (1+ε)-approximation algorithm for the Fréchet distance between two polygonal curves in ℝ d . To analyze this algorithm we introduce a new realistic family of curves, c-packed curves, that is closed under simplification. We believe the notion of c-packed curves to be of independent interest. We show that our algorithm has near linear running time for c-packed polygonal curves, and similar results for other input models, such as low-density polygonal curves.