---
_id: '4075'
abstract:
- lang: eng
text: A key problem in computational geometry is the identification of subsets of
a point set having particular properties. We study this problem for the properties
of convexity and emptiness. We show that finding empty triangles is related to
the problem of determining pairs of vertices that see each other in a star-shaped
polygon. A linear-time algorithm for this problem which is of independent interest
yields an optimal algorithm for finding all empty triangles. This result is then
extended to an algorithm for finding empty convex r-gons (r> 3) and for determining
a largest empty convex subset. Finally, extensions to higher dimensions are mentioned.
acknowledgement: The first author is pleased to acknowledge support by the National
Science Foundation under Grant CCR-8700917. The research of the second author was
supported by Amoco Foundation Faculty Development Grant CS 1-6-44862 and by the
National Science Foundatio
article_processing_charge: No
article_type: original
author:
- first_name: David
full_name: Dobkin, David
last_name: Dobkin
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Mark
full_name: Overmars, Mark
last_name: Overmars
citation:
ama: Dobkin D, Edelsbrunner H, Overmars M. Searching for empty convex polygons.
Algorithmica. 1990;5(4):561-571. doi:10.1007/BF01840404
apa: Dobkin, D., Edelsbrunner, H., & Overmars, M. (1990). Searching for empty
convex polygons. Algorithmica. Springer. https://doi.org/10.1007/BF01840404
chicago: Dobkin, David, Herbert Edelsbrunner, and Mark Overmars. “Searching for
Empty Convex Polygons.” Algorithmica. Springer, 1990. https://doi.org/10.1007/BF01840404.
ieee: D. Dobkin, H. Edelsbrunner, and M. Overmars, “Searching for empty convex polygons,”
Algorithmica, vol. 5, no. 4. Springer, pp. 561–571, 1990.
ista: Dobkin D, Edelsbrunner H, Overmars M. 1990. Searching for empty convex polygons.
Algorithmica. 5(4), 561–571.
mla: Dobkin, David, et al. “Searching for Empty Convex Polygons.” Algorithmica,
vol. 5, no. 4, Springer, 1990, pp. 561–71, doi:10.1007/BF01840404.
short: D. Dobkin, H. Edelsbrunner, M. Overmars, Algorithmica 5 (1990) 561–571.
date_created: 2018-12-11T12:06:47Z
date_published: 1990-06-01T00:00:00Z
date_updated: 2022-02-21T10:55:13Z
day: '01'
doi: 10.1007/BF01840404
extern: '1'
intvolume: ' 5'
issue: '4'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF01840404
month: '06'
oa_version: None
page: 561 - 571
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer
publist_id: '2049'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Searching for empty convex polygons
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 5
year: '1990'
...
---
_id: '4311'
article_processing_charge: No
author:
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
- first_name: A.
full_name: Clark, A.
last_name: Clark
citation:
ama: 'Barton NH, Clark A. Population structure and processes in evolution. In: Wöhrmann
K, Jain S, eds. Population Biology: Ecological and Evolutionary Viewpoints.
Springer; 1990:115-174. doi:10.1007/978-3-642-74474-7_5'
apa: 'Barton, N. H., & Clark, A. (1990). Population structure and processes
in evolution. In K. Wöhrmann & S. Jain (Eds.), Population biology: Ecological
and evolutionary viewpoints (pp. 115–174). Springer. https://doi.org/10.1007/978-3-642-74474-7_5'
chicago: 'Barton, Nicholas H, and A. Clark. “Population Structure and Processes
in Evolution.” In Population Biology: Ecological and Evolutionary Viewpoints,
edited by Klaus Wöhrmann and Subodh Jain, 115–74. Springer, 1990. https://doi.org/10.1007/978-3-642-74474-7_5.'
ieee: 'N. H. Barton and A. Clark, “Population structure and processes in evolution,”
in Population biology: Ecological and evolutionary viewpoints, K. Wöhrmann
and S. Jain, Eds. Springer, 1990, pp. 115–174.'
ista: 'Barton NH, Clark A. 1990.Population structure and processes in evolution.
In: Population biology: Ecological and evolutionary viewpoints. , 115–174.'
mla: 'Barton, Nicholas H., and A. Clark. “Population Structure and Processes in
Evolution.” Population Biology: Ecological and Evolutionary Viewpoints,
edited by Klaus Wöhrmann and Subodh Jain, Springer, 1990, pp. 115–74, doi:10.1007/978-3-642-74474-7_5.'
short: 'N.H. Barton, A. Clark, in:, K. Wöhrmann, S. Jain (Eds.), Population Biology:
Ecological and Evolutionary Viewpoints, Springer, 1990, pp. 115–174.'
date_created: 2018-12-11T12:08:11Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-16T10:49:05Z
day: '01'
doi: 10.1007/978-3-642-74474-7_5
editor:
- first_name: Klaus
full_name: Wöhrmann, Klaus
last_name: Wöhrmann
- first_name: Subodh
full_name: Jain, Subodh
last_name: Jain
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/book/10.1007/978-3-642-74474-7
month: '01'
oa_version: None
page: 115 - 174
publication: 'Population biology: Ecological and evolutionary viewpoints'
publication_identifier:
isbn:
- ' 978-3642744761'
publication_status: published
publisher: Springer
publist_id: '1748'
quality_controlled: '1'
status: public
title: Population structure and processes in evolution
type: book_chapter
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1990'
...
---
_id: '4310'
article_processing_charge: No
article_type: original
author:
- first_name: Nicholas H
full_name: Barton, Nicholas H
id: 4880FE40-F248-11E8-B48F-1D18A9856A87
last_name: Barton
orcid: 0000-0002-8548-5240
- first_name: Steve
full_name: Jones, Steve
last_name: Jones
citation:
ama: Barton NH, Jones S. The language of the genes. Nature. 1990;346:415-416.
doi:10.1038/346415a0
apa: Barton, N. H., & Jones, S. (1990). The language of the genes. Nature.
Nature Publishing Group. https://doi.org/10.1038/346415a0
chicago: Barton, Nicholas H, and Steve Jones. “The Language of the Genes.” Nature.
Nature Publishing Group, 1990. https://doi.org/10.1038/346415a0.
ieee: N. H. Barton and S. Jones, “The language of the genes,” Nature, vol.
346. Nature Publishing Group, pp. 415–416, 1990.
ista: Barton NH, Jones S. 1990. The language of the genes. Nature. 346, 415–416.
mla: Barton, Nicholas H., and Steve Jones. “The Language of the Genes.” Nature,
vol. 346, Nature Publishing Group, 1990, pp. 415–16, doi:10.1038/346415a0.
short: N.H. Barton, S. Jones, Nature 346 (1990) 415–416.
date_created: 2018-12-11T12:08:11Z
date_published: 1990-08-02T00:00:00Z
date_updated: 2022-02-16T10:51:50Z
day: '02'
doi: 10.1038/346415a0
extern: '1'
intvolume: ' 346'
language:
- iso: eng
main_file_link:
- url: https://www.nature.com/articles/346415a0
month: '08'
oa_version: None
page: 415 - 416
publication: Nature
publication_identifier:
eissn:
- 1476-4687
issn:
- 0028-0836
publication_status: published
publisher: Nature Publishing Group
publist_id: '1749'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The language of the genes
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 346
year: '1990'
...
---
_id: '4510'
abstract:
- lang: eng
text: "The interleaving model is both adequate and sufficiently abstract to allow
for the practical specification and verification of many properties of concurrent
systems. We incorporate real time into this model by defining the abstract notion
of a real-time transition system as a conservative extension of traditional transition
systems: qualitative fairness requirements are replaced (and superseded) by quantitative
lower-bound and upper-bound real-time requirements for transitions.\r\nWe present
proof rules to establish lower and upper real-time bounds for response properties
of real-time transition systems. This proof system can be used to verify bounded-invariance
and bounded-response properties, such as timely termination of shared-variables
multi-process systems, whose semantics is defined in terms of real-time transition
systems."
acknowledgement: 'Sponsors: IBM graduate fellowship, National Science Foundation
grant CCR-89-11512, National Science Foundation CCR-89-13641, Defense Advanced
Research Projects Agency under contract N00039-84-C-0211, United States Air Force
Office of Scientific Research under contract AFOSR-90-0057, European Community
ESPRIT Basic Research Action project 3096 (SPEC).'
article_processing_charge: No
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Zohar
full_name: Manna, Zohar
last_name: Manna
- first_name: Amir
full_name: Pnueli, Amir
last_name: Pnueli
citation:
ama: 'Henzinger TA, Manna Z, Pnueli A. An interleaving model for real time. In:
Proceedings of the 5th Jerusalem Conference on Information Technology.
IEEE; 1990:717-730. doi:10.1109/JCIT.1990.128356'
apa: 'Henzinger, T. A., Manna, Z., & Pnueli, A. (1990). An interleaving model
for real time. In Proceedings of the 5th Jerusalem Conference on Information
Technology (pp. 717–730). Jerusalem, Israel: IEEE. https://doi.org/10.1109/JCIT.1990.128356'
chicago: Henzinger, Thomas A, Zohar Manna, and Amir Pnueli. “An Interleaving Model
for Real Time.” In Proceedings of the 5th Jerusalem Conference on Information
Technology, 717–30. IEEE, 1990. https://doi.org/10.1109/JCIT.1990.128356.
ieee: T. A. Henzinger, Z. Manna, and A. Pnueli, “An interleaving model for real
time,” in Proceedings of the 5th Jerusalem Conference on Information Technology,
Jerusalem, Israel, 1990, pp. 717–730.
ista: 'Henzinger TA, Manna Z, Pnueli A. 1990. An interleaving model for real time. Proceedings
of the 5th Jerusalem Conference on Information Technology. JCIT: Jerusalem Conference
on Information Technology, 717–730.'
mla: Henzinger, Thomas A., et al. “An Interleaving Model for Real Time.” Proceedings
of the 5th Jerusalem Conference on Information Technology, IEEE, 1990, pp.
717–30, doi:10.1109/JCIT.1990.128356.
short: T.A. Henzinger, Z. Manna, A. Pnueli, in:, Proceedings of the 5th Jerusalem
Conference on Information Technology, IEEE, 1990, pp. 717–730.
conference:
end_date: 1990-10-25
location: Jerusalem, Israel
name: 'JCIT: Jerusalem Conference on Information Technology'
start_date: 1990-10-22
date_created: 2018-12-11T12:09:14Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-15T15:51:25Z
day: '01'
doi: 10.1109/JCIT.1990.128356
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://ieeexplore.ieee.org/abstract/document/128356
month: '01'
oa_version: None
page: 717 - 730
publication: ' Proceedings of the 5th Jerusalem Conference on Information Technology'
publication_identifier:
isbn:
- 0-8186-2078-1
publication_status: published
publisher: IEEE
publist_id: '220'
quality_controlled: '1'
scopus_import: '1'
status: public
title: An interleaving model for real time
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1990'
...
---
_id: '4522'
abstract:
- lang: eng
text: 'We introduce a novel extension of propositional modal logic that is interpreted
over Kripke structures in which a value is associated with every possible world.
These values are. however, not treated as full first-order objects: they can be
accessed only by a very restricted form of quantification: the "freeze" quantifier
binds a variable to the value of the current world. We present a complete proof
system for this ("half-order") modal logic. As a special case, we obtain the real-time
temporal logic TPTL of [AH891: the models are restricted to infinite sequences
of states, whose values are monotonically increasing natural numbers. The ordering
relation between states is interpreted as temporal precedence. while the value
associated with a state is interpreted as its "rear time. We extend our proof
system to be complete for TPTL. and demonstrate how it can be used to derive real-time
properties. '
acknowledgement: Many thanks to Rajeev Alur, Adam Grove, Zohar Manna, and Amir Pnueli
for their continuous discussions and support.
article_processing_charge: No
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: 'Henzinger TA. Half-order modal logic: How to prove real-time properties. In:
Proceedings of the 9th Annual ACM Symposium on Principles of Distributed Computing.
ACM; 1990:281-296. doi:10.1145/93385.93429'
apa: 'Henzinger, T. A. (1990). Half-order modal logic: How to prove real-time properties.
In Proceedings of the 9th annual ACM symposium on Principles of distributed
computing (pp. 281–296). Quebec City, Canada: ACM. https://doi.org/10.1145/93385.93429'
chicago: 'Henzinger, Thomas A. “Half-Order Modal Logic: How to Prove Real-Time Properties.”
In Proceedings of the 9th Annual ACM Symposium on Principles of Distributed
Computing, 281–96. ACM, 1990. https://doi.org/10.1145/93385.93429.'
ieee: 'T. A. Henzinger, “Half-order modal logic: How to prove real-time properties,”
in Proceedings of the 9th annual ACM symposium on Principles of distributed
computing, Quebec City, Canada, 1990, pp. 281–296.'
ista: 'Henzinger TA. 1990. Half-order modal logic: How to prove real-time properties.
Proceedings of the 9th annual ACM symposium on Principles of distributed computing.
PODC: Principles of Distributed Computing, 281–296.'
mla: 'Henzinger, Thomas A. “Half-Order Modal Logic: How to Prove Real-Time Properties.”
Proceedings of the 9th Annual ACM Symposium on Principles of Distributed Computing,
ACM, 1990, pp. 281–96, doi:10.1145/93385.93429.'
short: T.A. Henzinger, in:, Proceedings of the 9th Annual ACM Symposium on Principles
of Distributed Computing, ACM, 1990, pp. 281–296.
conference:
end_date: 1990-08-24
location: Quebec City, Canada
name: 'PODC: Principles of Distributed Computing'
start_date: 1990-08-22
date_created: 2018-12-11T12:09:17Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2022-02-15T15:11:03Z
day: '01'
doi: 10.1145/93385.93429
extern: '1'
language:
- iso: eng
main_file_link:
- url: https://dl.acm.org/doi/10.1145/93385.93429
month: '01'
oa_version: None
page: 281 - 296
publication: Proceedings of the 9th annual ACM symposium on Principles of distributed
computing
publication_identifier:
isbn:
- 978-0-89791-404-8
publication_status: published
publisher: ACM
publist_id: '209'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Half-order modal logic: How to prove real-time properties'
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1990'
...