Article

Free access

Space-time tradeoffs for emptiness queries (extended abstract)

Author:

Jeff EricksonAuthors Info & Claims

SCG '97: Proceedings of the thirteenth annual symposium on Computational geometry

Pages 304 - 313

https://doi.org/10.1145/262839.262988

Published: 01 August 1997 Publication History

First page of PDF

References

[1]

P. K. Agarwal. Range searching. Report CS-1996- 05, Dept. Comput. Sci., Duke Univ., 1996. http:// www.cs.duke.edu/-pankaj/papers/range-survey.ps.gz. To appear in The CRC Hur#dbook of D#cref.e arLd Comp#io,a# Geome#, J. E. Goodman and J. O'R#urke, editors, CRC Press.

Digital Library

[2]

P. K. Agarwal and J. Matou#k. Ray shooting and parametric search. SIAM J. Comp#t. 22(4):794-806, 1993.

Digital Library

[3]

A. Aggarwal, M. Hansen, and T. Leighton. Solving query-retrieval problems by compacting Voronoi diagrams. Proc. F2nd Annu. A CM Sympos. Theory Comput, pp. 331-340, 1990.

Digital Library

[4]

M. Ben-Or. Lower bounds for algebraic computation trees. Proc. 15th Annu. ACM Sympos. Theory Cornput., pp. 80-86, 1983.

Digital Library

[5]

M. de Berg, M. Overmars, and O. Schwarzkopf. Computing and verifying depth orders. SIAM J. Comput 23:437-446, 1994.

Digital Library

[6]

H. Br6nnimann, B. Chazelle, and J. Pach. How hard is halfspace range searching? Discrete Comput Geom. I0:143--155, 1993.

[7]

T. M. Chan. Fixed-dimensional linear programming queries made easy. Proc. 12th Annu. ACM Sympos. Comput Geom., pp. 284-290, 1996.

Digital Library

[8]

T. M. Chart. Output-sensitive results on convex hulls, extreme points, and related problems. Discrete Cornput Geom. 16:369--387, 1996.

Digital Library

[9]

B. Chazelle. Lower bounds on the complexity of polytope range searching. J. Amer. Ma#h. Soc. 2:637--666, 1989.

[10]

B. Chazelle. Cutting hyperplanes for divide-andconquer. Discref, e Corr#put,. Geom. 9(2):145-158, 1993.

Digital Library

[11]

B. Chazelle, H. Edelsbrnnner, L. Guibas, and M. Sharir. Algorithms for bichromatic line segment problems and polyhedral terrains. Algori#hmica 11:116-132, 1994.

[12]

B. Chazelle and J. Friedman. Point location among hyperplanes and unidirectional ray-shooting. Comput. Geom. Theory Appl. 4:53-62, 1994.

Digital Library

[13]

B. Chazelle, L. J. Guibas, and D. T. Lee. The power of geometric duality. BIT 25:76-90, 1985.

Digital Library

[14]

B. Chazelle and B. Rosenberg. Simplex range reporting on a pointer machine. Comput Geom. Theory Appl. 5:237-247, 1996.

Digital Library

[15]

B. Chazelle. Lower bounds for off-line range searching. Discrete Comput Geom. 17(1):53-66, 1997.

Digital Library

[16]

D. P. Dobkin and D. G. Kirkpatrick. Determining the separation of preprocessed polyhedra- a unified approach. Proc. 17th Inter'nat. Colloq. Automata Lang. Program., pp. 400-413. Springer-Verlag, Lecture Notes in Computer Science 443, 1990.

Digital Library

[17]

R. Dwyer and W. Eddy. Maximal empty ellipsoids. Internat. J. Comput. Geom. Appl. 6:169--186, 1996.

[18]

J. Erickson. New lower bounds for halfspace emptiness. Proc. 37#h Annu. IEEE Syrnpo$. Found. Cornput. Sci., pp. 472-481, 1996.

Digital Library

[19]

J. Erickson. New lower bounds for Hopcroft's problem. Discrete Comput. Geom. 16:389-418, 1996.

Digital Library

[20]

M. L. Fredman. Lower bounds on the complexity of some optimal data structures. SIAM J. Comput 10:1- 10, 1981.

Digital Library

[21]

J. Matou#ek. Efficient partition trees. Discrete Cornput Geom. 8:315-334, 1992.

Digital Library

[22]

J. Matotu#ek. Reporting points in halfspaces. Comput Geom. Theory Appl. 2(3):169--186, 1992.

Digital Library

[23]

J. MatouJek. Linear optimization queries. J. Algor/t#ms 14:432--448, 1993.

Digital Library

[24]

J. Matouiek. On vertical ray shooting in arrangements. Comput Geom. Theory Appl. 2(5):279-285, Mar. 1993.

Digital Library

[25]

J. Matou#k. Range searching with efficient hierarchical cuttings. Discrete Comput Geom. 10(2):157-182, 1993.

Digital Library

[26]

J. Matouiek. Geometric range searching. A CM Cornput Surv. 26:421-461, 1994.

Digital Library

[27]

J. Mato# and O. Schwarzkopf. On ray shooting in convex polytopes. Discrete Comput Geom. 10(2):215- 232, 1993.

Digital Library

[28]

J. Pach and P. K. Agarwal. Combinatorial Geometry. John Wiley & Sons, New York, NY, 1995.

[29]

F. P. Preparata and M. I. Shamos. Computa$ional Geome#ry: An Introduction. Springer-Verlag, New York, NY, 1985.

Digital Library

[30]

R. E. Tarjan. A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput Syst Sc/. 18:110-127, 1979.

[31]

A. C. Yao. On the complexity of maintaining partial sums. SIAM J. Comput 14:277-288, 1985.

Digital Library

Cited By

Barequet GGoodrich MChen DDaescu OSnoeyink JJanardan R(1998)Efficiently approximating polygonal paths in three and higher dimensionsProceedings of the fourteenth annual symposium on Computational geometry10.1145/276884.276920(317-326)Online publication date: 7-Jun-1998
https://dl.acm.org/doi/10.1145/276884.276920

Index Terms

Space-time tradeoffs for emptiness queries (extended abstract)
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Punctured super-orthogonal space-time trellis codes

In this paper, we propose punctured super-orthogonal space-time trellis codes. First, considering a system with two transmit antennas, we present the basic design criteria for the punctured super-orthogonal codes. Then, staged decoding, a sub-optimal ...
Multigroup ML decodable collocated and distributed space-time block codes

In this paper, collocated and distributed space-time block codes (DSTBCs) which admit multigroup maximum-likelihood (ML) decoding are studied. First, the collocated case is considered and the problem of constructing space-time block codes (STBCs) which ...
Novel full diversity space time codes

A novel full diversity space-time trellis code, referred to as an assembled space-time trellis code (ASTTC), is presented in this letter. For this scheme, space-time trellis coded signals are first linearly transformed, and then the transformed signals ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '97: Proceedings of the thirteenth annual symposium on Computational geometry

August 1997

490 pages

ISBN:0897918789

DOI:10.1145/262839

Chairman:
Jean-Daniel Boissonnat
INRIA Sophia-Antipolis

Copyright © 1997 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SoCG97

Sponsor:

SoCG97: 13th ACM Symposium on Computational Geometry

June 4 - 6, 1997

Nice, France

Acceptance Rates

SCG '97 Paper Acceptance Rate 75 of 199 submissions, 38%;

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
319
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)2

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Barequet GGoodrich MChen DDaescu OSnoeyink JJanardan R(1998)Efficiently approximating polygonal paths in three and higher dimensionsProceedings of the fourteenth annual symposium on Computational geometry10.1145/276884.276920(317-326)Online publication date: 7-Jun-1998
https://dl.acm.org/doi/10.1145/276884.276920

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents