Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Computational Geometry
Informing Science
New Jersey
Property Testing
Related Publications
(7)
Regular Languages Are Testable with a Constant Number of Queries
Property Testing and Its Connection to Learning and Approximation
Robust Characterizations of Polynomials with Applications to Program Testing
Efficient Testing of Large Graphs
Property Testing with Geometric Queries
Subscribe
Academic
Publications
Property Testing in Computational Geometry
Property Testing in Computational Geometry,10.1007/3540452532_15,Artur Czumaj,Christian Sohler,Martin Ziegler
Edit
Property Testing in Computational Geometry
(
Citations: 26
)
BibTex

RIS

RefWorks
Download
Artur Czumaj
,
Christian Sohler
,
Martin Ziegler
)Artur Czumaj1, Christian Sohler2, and Martin Ziegler21Department of Computer and Information Science,
New Jersey
Institute of Technology,Newark, NJ 071021982, USA. czumaj@cis.njit.edu2Heinz Nixdorf Institute and Department of Mathematics & Computer Science, University ofPaderborn, D33095 Paderborn, Germany. csohler,ziegler@unipaderborn.deAbstract. We consider the notion of
property testing
as applied to computationalgeometry. We aim at developing efficient...
Conference:
European Symposium on Algorithms  ESA
, pp. 155166, 2000
DOI:
10.1007/3540452532_15
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
Citation Context
(20)
...Many property querying or testing algorithms [4], [
5
], [6] use sublinearity in order to test or query properties of massive graphs...
Lantao Liu
,
et al.
Approximate characterization of multirobot 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 intersectionfree: 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 Czumaj
,
et al.
Sublineartime 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 Hellweg
,
et 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 Alon
,
et 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, SpringerVerlag, Berlin, 2000 [
6
]...
...Recently, (after publishing the preliminary version [
6
] of the current paper) three sublineartime approximation algorithms have been presented for the problem of estimating the weight of the MST...
Artur Czumaj
,
et al.
Testing Euclidean minimum spanning trees in the plane
References
(22)
Property testing in bounded degree graphs
(
Citations: 189
)
Oded Goldreich
,
Dana Ron
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 406415, 1997
Robust Characterizations of Polynomials with Applications to Program Testing
(
Citations: 300
)
Ronitt Rubinfeld
,
Madhu Sudan
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 25, no. 2, pp. 252271, 1996
Approximate Checking of Polynomials and Functional Equations
(
Citations: 6
)
F. Ergun
,
S. Ravi Kumar
,
R. Rubinfeld
Published in 1996.
Approximate Checking of Polynomials and Functional Equations (extended abstract)
(
Citations: 5
)
Funda Ergün
,
Ravi Kumar
,
Ronitt Rubinfeld
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 592601, 1996
Checking geometric programs or verification of geometric structures
(
Citations: 49
)
Kurt Mehlhorn
,
Stefan Näher
,
Thomas Schilz
,
Stefan Schirra
,
Michael Seel
,
Raimund Seidel
,
Christian Uhrig
Conference:
Symposium on Computational Geometry  SOCG
, pp. 159165, 1996
Sort by:
Citations
(26)
Approximate characterization of multirobot swarm “shapes” in sublineartime
Lantao Liu
,
Benjamin Fine
,
Dylan Shell
,
Andreas Klappenecker
Conference:
International Conference on Robotics and Automation  ICRA
, pp. 28862891, 2011
Sublineartime Algorithms
(
Citations: 18
)
Artur Czumaj
,
Christian Sohler
Journal:
Bulletin of The European Association for Theoretical Computer Science  EATCS
, pp. 4164, 2010
Testing Euclidean Spanners
Frank Hellweg
,
Melanie Schmidt
,
Christian Sohler
Conference:
European Symposium on Algorithms  ESA
, pp. 6071, 2010
A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
(
Citations: 10
)
Noga Alon
,
Eldar Fischer
,
Ilan Newman
,
Asaf Shapira
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 39, no. 1, 2009
Testing Euclidean minimum spanning trees in the plane
(
Citations: 2
)
Artur Czumaj
,
Christian Sohler
Journal:
ACM Transactions on Algorithms  TALG
, vol. 4, no. 3, pp. 123, 2008