Academic
Publications
Property Testing in Computational Geometry

Property Testing in Computational Geometry,10.1007/3-540-45253-2_15,Artur Czumaj,Christian Sohler,Martin Ziegler

Property Testing in Computational Geometry   (Citations: 26)
BibTex | RIS | RefWorks Download
)Artur Czumaj1, Christian Sohler2, and Martin Ziegler21Department of Computer and Information Science, New Jersey Institute of Technology,Newark, NJ 07102-1982, USA. czumaj@cis.njit.edu2Heinz Nixdorf Institute and Department of Mathematics & Computer Science, University ofPaderborn, D-33095 Paderborn, Germany. csohler,ziegler@uni-paderborn.deAbstract. We consider the notion of property testing as applied to computationalgeometry. We aim at developing efficient...
Conference: European Symposium on Algorithms - ESA , pp. 155-166, 2000
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Many property querying or testing algorithms [4], [5], [6] use sublinearity in order to test or query properties of massive graphs...

    Lantao Liuet al. Approximate characterization of multi-robot swarm “shapes” in sublinea...

    • ...Czumaj et al. [23] gave a simple algorithm that for any ε > 0, can distinguish between the case when A and B do not intersect, and the case when at least ε n points has to be removed from A and B to make them intersection-free: the algorithm returns the outcome of a test if a random sample of O((d/ε) log(d/ε)) points from A intersects with a random sample of O((d/ε) log(d/ε)) points from B...

    Artur Czumajet al. Sublinear-time Algorithms

    • ...Previous work on geometric property testing includes testing algorithms for convexity of polygons [21], convexity [33], geometric properties of point sets (for example convex position), the Euclidean minimum spanning tree [18,17,19], and clusterability of point sets [1,17]...

    Frank Hellweget al. Testing Euclidean Spanners

    • ...Following [26, 11, 35] property testing was studied in various other contexts such as boolean functions [4, 18, 21, 20, 30, 32], geometric objects [2, 13] and algebraic structures [11, 22, 23, 9]. See the surveys [16, 34] for additional results and references...

    Noga Alonet al. A Combinatorial Characterization of the Testable Graph Properties: It'...

    • ...The results presented in this paper appeared in a preliminary form as a part of the paper “Property testing in computational geometry,” in Proceedings of the 8th Annual European Symposium on Algorithms (ESA’00), pages 155‐166, volume 1879 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, 2000 [6]...
    • ...Recently, (after publishing the preliminary version [6] of the current paper) three sublinear-time approximation algorithms have been presented for the problem of estimating the weight of the MST...

    Artur Czumajet al. Testing Euclidean minimum spanning trees in the plane

Sort by: