Article

Free access

Output-size sensitive algorithms for finding maximal vectors

Authors:

David G. Kirkpatrick,

Raimund SeidelAuthors Info & Claims

SCG '85: Proceedings of the first annual symposium on Computational geometry

Pages 89 - 96

https://doi.org/10.1145/323233.323246

Published: 01 June 1985 Publication History

PDF eReader

References

[1]

{AHU} A. V. Aho, J. E. Hopcroft, and J. D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA (1974).

Digital Library

Google Scholar

[2]

{B} M. Ben-Or: Lower Bounds for Algebraic Computation Trees. Proc. 15th ACM STOC; pp. 80-86; 1983.

Digital Library

Google Scholar

[3]

{BS} J. L. Bentley and M. I. Shamos: Divide and Conquer for Linear Expected Time. Information Processing Letters 7, (1978) 87-91.

Crossref

Google Scholar

[4]

{BKST} J. L. Bentley, H. T. Kung, M. Schkolnick, and C. D. Thompson: On the Average Number of Maxima in a Set of Vectors and Applications. JACM 25; pp. 536-543; 1978.

Digital Library

Google Scholar

[5]

{GBT} H. N. Gabow, J. L. Bentley, and R. E. Tarjan: Sealing and Related Techniques for Geometry Problems . Proc. 16th ACM STOC; pp. 135-143; 1984.

Digital Library

Google Scholar

[6]

{KS} D. G. Kirkpatrick and R. Seidel: The Ultimate Planar Convex Hull Algorithm? Cornell CS Tech. Rep. 83-577; to appear in SIAM J. on Computing.

Digital Library

Google Scholar

[7]

{KLP} H. T. Kung, F. Luccio, and F. P. Preparata: On Finding the Maxima of a Set of Vectors. JACM 22; pp. 469-476; 1975.

Digital Library

Google Scholar

[8]

{R} P. Ramanan: Private Communication.

Google Scholar

Cited By

View all

Akram WSaxena S(2024)Maximizing Weighted Dominance in the PlaneTheoretical Aspects of Computing – ICTAC 202410.1007/978-3-031-77019-7_9(153-163)Online publication date: 22-Nov-2024
https://doi.org/10.1007/978-3-031-77019-7_9
Cabello S(2023)Faster distance-based representative skyline and k-center along pareto front in the planeJournal of Global Optimization10.1007/s10898-023-01280-186:2(441-466)Online publication date: 16-Mar-2023
https://dl.acm.org/doi/10.1007/s10898-023-01280-1
Liu JXiong LPei JLuo JZhang HYu W(2021)Group-Based Skyline for Pareto Optimal GroupsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2019.296034733:7(2914-2929)Online publication date: 1-Jul-2021
https://doi.org/10.1109/TKDE.2019.2960347
Show More Cited By

Index Terms

Output-size sensitive algorithms for finding maximal vectors
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

A Linear-Time Algorithm for Finding a Maximal Planar Subgraph

We construct an optimal linear-time algorithm for the maximal planar subgraph problem: given a graph G, find a planar subgraph G' of G such that adding to G' an extra edge of G results in a nonplanar graph. Our solution is based on a fast data structure ...
Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs

There is substantial literature dealing with fixed parameter algorithms for the dominating set problem on various families of graphs. In this paper, we give a k ^O(dk) n time algorithm for finding a dominating set of size at most k in a d-degenerated ...
On acyclically 4-colorable maximal planar graphs

An acyclic coloring of a graph is a proper coloring of the graph, for which every cycle uses at least three colors. Let G4 be the set of maximal planar graphs of minimum degree 4, such that each graph in G4 contains exactly four odd-vertices and the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SCG '85: Proceedings of the first annual symposium on Computational geometry

June 1985

322 pages

ISBN:0897911636

DOI:10.1145/323233

Chairman:
Joseph O'Rourke
Johns Hopkins Univ., Baltimore, MD

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1985

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SCG85

Sponsor:

SCG85: The 1st Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry 1985

June 5 - 7, 1985

Maryland, Baltimore, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

51
Total Citations
View Citations
593
Total Downloads

Downloads (Last 12 months)74
Downloads (Last 6 weeks)6

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Akram WSaxena S(2024)Maximizing Weighted Dominance in the PlaneTheoretical Aspects of Computing – ICTAC 202410.1007/978-3-031-77019-7_9(153-163)Online publication date: 22-Nov-2024
https://doi.org/10.1007/978-3-031-77019-7_9
Cabello S(2023)Faster distance-based representative skyline and k-center along pareto front in the planeJournal of Global Optimization10.1007/s10898-023-01280-186:2(441-466)Online publication date: 16-Mar-2023
https://dl.acm.org/doi/10.1007/s10898-023-01280-1
Liu JXiong LPei JLuo JZhang HYu W(2021)Group-Based Skyline for Pareto Optimal GroupsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2019.296034733:7(2914-2929)Online publication date: 1-Jul-2021
https://doi.org/10.1109/TKDE.2019.2960347
Liu JYang JXiong LPei JLuo JGuo YMa SFan C(2021)Skyline Diagram: Efficient Space Partitioning for Skyline QueriesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2019.292391433:1(271-286)Online publication date: 1-Jan-2021
https://doi.org/10.1109/TKDE.2019.2923914
Barbay JPérez-Lantero PRojas-Ledesma J(2021)Computing the depth distribution of a set of boxesTheoretical Computer Science10.1016/j.tcs.2021.06.007883(69-82)Online publication date: Sep-2021
https://doi.org/10.1016/j.tcs.2021.06.007
Choi JCabello SAhn H(2021)Maximizing Dominance in the Plane and its ApplicationsAlgorithmica10.1007/s00453-021-00863-2Online publication date: 13-Aug-2021
https://doi.org/10.1007/s00453-021-00863-2
Yu WLiu JPei JXiong LChen XQin Z(2020)Efficient Contour Computation of Group-Based SkylineIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2019.290523932:7(1317-1332)Online publication date: 1-Jul-2020
https://doi.org/10.1109/TKDE.2019.2905239
Groz BMallmann-Trenn FMathieu CVerdugo V(2020)Skyline Computation with Noisy ComparisonsCombinatorial Algorithms10.1007/978-3-030-48966-3_22(289-303)Online publication date: 8-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-48966-3_22
Liu JYang JXiong LPei J(2019)Secure and Efficient Skyline Queries on Encrypted DataIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2018.285747131:7(1397-1411)Online publication date: 1-Jul-2019
https://doi.org/10.1109/TKDE.2018.2857471
Liu JYang JXiong LPei JLuo J(2018)Skyline Diagram: Finding the Voronoi Counterpart for Skyline Queries2018 IEEE 34th International Conference on Data Engineering (ICDE)10.1109/ICDE.2018.00065(653-664)Online publication date: Apr-2018
https://doi.org/10.1109/ICDE.2018.00065
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

A Linear-Time Algorithm for Finding a Maximal Planar Subgraph

Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs

On acyclically 4-colorable maximal planar graphs